Cho số nguyên dương ~n~. Hãy đếm số bít ~1~ trong biểu diễn nhị phân của các số nguyên từ ~1~ đến ~n~. Ví dụ với ~n = 6~ thì các biểu diễn nhị phân của ~1 \dots 6~ là ~1~, ~10~, ~11~, ~100~, ~101~ và ~110~, do đó có tổng cộng ~9~ bít ~1~.

Dữ liệu:

Cho trong file BITSUM.INP chỉ chứa một số nguyên dương ~n~

Kết quả:

Ghi vào tệp văn bản BITSUM.OUT số bit ~1~ trong biểu diễn nhị phân của các số nguyên từ ~1~ đến ~n~.

Ví dụ:

INPUT

6

OUTPUT

9

Ràng buộc:

• ~50\%~ test với ~n \leq 100~
• ~50\%~ test với ~n \leq 10^12~
• Thời gian thực hiện chương trình không quá ~2~ giây