Bạn được cho một số nguyên ~n~. Hãy đếm tổng số bit 1 trong biểu diễn nhị phân của tất cả các số nguyên từ 1 đến ~n~.

Đầu vào:

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

Đầu ra:

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

Ràng buộc:

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

Ví dụ :

Input:

7

Output:

12

Giải thích: Các số từ 1 đến 7 và biểu diễn nhị phân của chúng:

1 ~=>~ 1 (1 bit 1)

2 ~=>~ 10 (1 bit 1)

3 ~=>~ 11 (2 bit 1)

4 ~=>~ 100 (1 bit 1)

5 ~=>~ 101 (2 bit 1)

6 ~=>~ 110 (2 bit 1)

7 ~=>~ 111 (3 bit 1)

Tổng cộng: 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12