Degree

The programming language interpreter for Base_ABC can handle assignments of the form A := B × C (where A, B, and C are variable names), but it cannot perform exponentiation directly. Therefore, to compute an expression like A^N, it must be broken down into a sequence of multiplication operations.

For instance, to compute X := A^5, you can use the following sequence of three multiplication commands:

1. R1 := A × A

2. R2 := A × R1

3. X := R1 × R2

Given a number N, your task is to determine the minimum number of multiplication commands required to compute A^N.

The input file will contain the integer N (where 2 ≤ N ≤ 2000).The output file should contain a single number, which is the minimum number of multiplication commands needed.

Examples