Banmkh6 là một người bị ám ảnh bởi những con số, anh ấy thường nghĩ ra những bài toán liên quan tới những chữ số quái dị, và đây là một đề bài tương tự:

"Tôi có một số n và tôi muốn tách n thành tổng của các số nhị phân "

Biết rằng số nhị phân là các số mà các chữ số của nó chỉ bao gồm 0 và 1, và không bắt đầu bằng số 0(ngoại trừ số 0). Ví dụ số 10 11000 101 là các số nhị phân, nhưng các số 2 23 1201 lại không phải là số nhị phân.

Và yêu cầu của Ban là tìm số lượng số nhị phân ít nhất sao cho tổng của chúng là n.

Ví dụ n = 21 = 10 + 11 => số lượng số nhị phân ít nhất mà tổng bằng 21 là 2.

Subtasks

• Subtasks 1: ~1 \leq n \leq 10^{6}~
• Subtasks 2: ~1 \leq n \leq 10^{18}~

Input

Dòng đầu tiên chứa 1 số nguyên n.

Output

Số lượng số nhị phân ít nhất mà tổng bằng n.

*Sample Input *

21

*Sample Output *

2