ami và cuom1999 đang tạo ra một ngôn ngữ lập trình mới. Ngôn ngữ hiện tại chỉ hỗ trợ các phép tính +, -, << (trong C++). Trong đó: 

a + b trả về tổng 2 số

a - b trả về hiệu 2 số

a << b trả về a * (2^b)

Ví dụ 1 << 5 = 32, 3 << 0 = 3.

ami và cuom1999 muốn cài đặt phép nhân cho ngôn ngữ dựa trên 3 phép toán trên. Chẳng hạn

a * 7  có thể tính bằng a * 8 - a hoặc a * 4 + a * 2 + a. Phép tính thứ nhất chỉ có 2 số hạng, trong khi phép tính thứ 2 có 3 số hạng. Từ đó 2 bạn đặt ra bài toán: làm sao để phép nhân sử dụng ít phép toán nhất có thể. Nói cách khác, cho một số tự nhiên n, hãy biểu diễn n thành tổng và hiệu của ít số hạng có dạng 2^k nhất.

Input:

Gồm một số tự nhiên n (0 <= n <= 10⁶).

Output:

In ra số lượng số hạng ít nhất cần dùng để biểu diễn n.