Nhiệm vụ của bạn là đếm số lượng bit 1 trong biểu diễn nhị phân của các số nguyên từ ~1~ đến ~n~.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số lượng bit 1 trong biểu diễn nhị phân của các số nguyên từ ~1~ đến ~n~.

Giới hạn

• ~1 \le n \le 10^{15}~

Ví dụ

Dữ liệu vào:

7

Kết quả:

12

Giải thích: Biểu diễn nhị phân của ~1 \ldots 7~ lần lượt là 1, 10, 11, 100, 101, 110 và 111, do đó có tổng cộng 12 bit 1.