Problem M. Minimal XOR Tree ≡

Statement

Petya has N vertices. He wants to connect them with edges to form a tree. Recall that a tree is a connected graph of N vertices and N − 1 edges.

When connecting the next pair of vertices, Petya calculates the curvature of the connection as xor(size_a, size_b), where size_a, size_b are the sizes of the subtrees being connected.

The curvature of a tree is the sum of the curvatures of all connections to construct this tree. Petya wants to minimize the curvature of the tree.

Note

The xor operation is a bitwise operation that results in one bits being in those digits that had different values.

Input format

The first line of input data contains an integer N — the number of nodes in the tree.

Output format

In a single line, print an integer — the minimum possible curvature of the tree.

Constraints

1 ≤ N ≤ 10⁹

Notes on samples

In the first example, only single vertices can be connected at first. The curvature of such a connection is xor(1, 1) = 0.

After this, two subtrees of 2 and 1 vertices can be connected. The curvature of such a connection is xor(2, 1) = 3.

The total curvature is equal to 3.

Sample tests

3

3

5

4

2

0