Xét dãy số tự nhiên từ \(1\) đến \(N\): \(1, 2, 3, 4, 5, 6, \dots, N\).

Ta biến đổi từng số trong dãy theo quy tắc sau:

• Nếu số đó là số lẻ thì giữ nguyên.
• Nếu số đó là số chẵn thì chia cho \(2\) liên tiếp cho đến khi nhận được một số lẻ, rồi dừng lại.

Ví dụ:

• \(1 \rightarrow 1\)
• \(2 \rightarrow 1\)
• \(4 \rightarrow 2 \rightarrow 1\)
• \(6 \rightarrow 3\)
• \(12 \rightarrow 6 \rightarrow 3\)
• \(40 \rightarrow 20 \rightarrow 10 \rightarrow 5\)

Yêu cầu: Cho số tự nhiên \(N\). Hãy tính tổng các số trong dãy mới sau khi đã biến đổi tất cả các số từ \(1\) đến \(N\).

Input

• Gồm một dòng chứa một số tự nhiên \(N\) (\(1 \le N \le 10^8\)).

Output

• Ghi ra một dòng chứa một số tự nhiên duy nhất là tổng cần tìm.

Example

6

14

10

36

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(N \le 1000\).
• \(30\%\) số test khác tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(N \le 10^6\).
• \(40\%\) số test còn lại tương ứng với \(40\%\) số điểm của bài thỏa mãn: \(N \le 10^8\).