Toto học về hệ đếm cơ số 2 và rất thích thú với các phép toán trên nó. Tichpx thấy vậy đặt ra bài toán, cho số nguyên dương n nếu viết tất cả các số từ 1 đến n sang hệ nhị phận thì cần bao nhiêu bit số 1. Toto rất hào hứng với bài toán nhưng vẫn chưa có lời giải. Bạn hãy lập trình giải bài toán giúp Toto nhé

Input

Một số nguyên dương n \((1 \le n \le 10^{15})\)

Output

Một số nguyên dương là số bit 1 cần dùng để có thể biểu diễn các số từ 1 đến n sang hệ nhị phân

Ví dụ

Input

10

Output

17

Ví dụ 2

Input

5

Output

7

Giải thích : Từ 1 đến 5 biểu diễn sang cơ số 2 thành 1, 10, 11, 100, 101 có tất cả 7 bit 1