Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of *n* vertices numbered from 0 to *n* - 1. For all 0 ≤ *u* &lt; *v* &lt; *n*, vertex *u* and vertex *v* are connected with an undirected edge that has weight <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b1dd244036db71efcfe46a5cd4ba74e2bd3f2935.png" style="max-width: 100.0%;max-height: 100.0%;"/> (where <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/c4b7092c0f7ce6535f2574569c98f7b3c2fe2c5f.png" style="max-width: 100.0%;max-height: 100.0%;"/> is the [bitwise-xor operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in [https://en.wikipedia.org/wiki/Complete_graph](https://en.wikipedia.org/wiki/Complete_graph)

You can read about the minimum spanning tree in [https://en.wikipedia.org/wiki/Minimum_spanning_tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.
The only line contains an integer *n* (2 ≤ *n* ≤ 10<sup class="upper-index">12</sup>), the number of vertices in the graph.
In the first sample: <img class="tex-graphics" src="https://espresso.codeforces.com/20e1655a0ec8e8d788bd2f5af92f93c968c65f3c.png" style="max-width: 100.0%;max-height: 100.0%;"/> The weight of the minimum spanning tree is 1+2+1=4.
4
4
10
21
2
1
1000000000000
20140978692096
999999999999
20140978692095
23131234
293058929
100000
877968
1024
5120
536870912
7784628224
536870911
7784628223
536870913
8321499136
123456789
1680249144
200
844
3
3
5
8
6
9
7
11
1000
5052
12000
84624
65536
524288
1048576
10485760
8
12
549755813888
10720238370816
549755813887
10720238370815
549755813889
11269994184704
n = int(input())
dp = [0] * (n + 1 if n >= 4 else 4)
dp[1] = 1
dp[2] = 1
dp[3] = 2
two_degree = 1
counter = 3
for i in range(4, n+1):
    if i - 1 == 2**(two_degree + 1):
        two_degree += 1
        dp[i] = 2**two_degree
    else:
        dp[i] = dp[i - 2**two_degree]
    counter += dp[i]
print(counter)
