Mr. Ganesh, a friend of Mr. Dengklek, give Mr. Dengklek a big matrix A dan asking the result of A^N. Because the matrix A is too big and Mr Dengklek doesn't have a lot of time, he wants to minimize the number of multiplication needed for computing A^N. In this case, assume Mr. Dengklek always stores the matrices that Mr. Dengklek ever computed, thus, if anytime Mr. Dengklek wants to use that matrix again, he can just directly use it without recomputing it.

You must help Mr. Dengklek to find out the minimum number of multiplication required to compute A^N.

Input

The first line consist of a single integer N (1 ≤ N ≤ 120).

Output

In the first line, output the result asked in the problem statement above.

Example Explanation

Here is one of the possible minimum calculation to get A^15.

Matrices that Mr. Dengklek have : A

1st multiplication : A * A = A^2

Matrices that Mr. Dengklek have : A, A^2

2nd multiplication : A*A^2 = A^3

Matrices that Mr. Dengklek have : A, A^2, A^3

3rd multiplication : A^3*A^3 = A^6

Matrices that Mr. Dengklek have : A, A^2, A^3, A^6

4th multiplication : A^6*A^6 = A^12

Matrices that Mr. Dengklek have : A, A^2, A^3, A^6,A^12

5th multiplication : A^12*A^3 = A^15

Example

Input:
15
Output:
5