Ông Nam muốn cân lại \(n\) viên bi sắt của mình để đem đi bán. Điều này được thực hiện trên cân Roberval nhiều lần, mỗi lần cân như sau:

• Nếu \(n\) chẵn thì thì chia thành \(n/2\) viên bi ở mỗi bên đĩa.
• Nếu \(n\) lẻ thì chia thành \((n - 1)/2\) viên bi ở mỗi bên đĩa, lẻ một viên để riêng.

Biết rằng trong \(n\) viên bi sắt có đúng một viên rỗng khối lượng nhẹ hơn những viên khác, các viên còn lại có khối lượng như nhau. Hỏi ông Nam cần cân tối đa bao nhiêu lần để tìm ra viên bi rỗng?

Đầu vào

Một số nguyên \(n\) duy nhất \((1 \le n \le 10^{18})\).

Đầu ra

Một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Đầu vào:

8

Đầu ra:

3