Bob wants to gift a pretty sequence to Amy!

For Bob, a sequence \(S\) of \(N\) terms is pretty when the \(i\)-th term \((2 \le i \le N)\) is a multiple of the previous term. In other words, \(S_{i} = k_i \times S_{i-1}\) for all \(2 \le i, k_i\). The first term will always be equal to 1.

In order to make it more special, the \(N\) terms should sum up to a given integer \(V\) and should be as long as possible.

Can you help Bob determine the maximum number of terms to make a pretty sequence that sums to exactly \(V\)?

Input Specification

The first line of the input will contain one integer \(V\) \((1 \le V \le 10^9)\), indicating the target sum of the terms.

Output Specification

Output one integer, which indicates the maximum size of the sequence that can form a pretty sequence. If Bob is unable to form such a sequence output -1. Note that \(N\) must be greater or equal to \(1\).

Subtasks

Note that you will be required to pass the sample input to receive points for the subtasks.

Subtask 1 [5%]

\(1 \le V \le 20\)

Subtask 2 [15%]

\(1 \le V \le 100\)

Subtask 3 [40%]

\(1 \le V \le 1\,000\)

Subtask 4 [40%]

No additional constraints.

Sample Input 1

16

Sample Output 1

3

Sample Explanation 1

One possible way to form the pretty sequence is using the following terms:

\[1, 5, 10\]

These add up to \(16\) and maximizes the number of terms.

Sample Input 2

8

Sample Output 1

2

Sample Explanation 1

The only way to form a pretty sequence is using the following terms:

\[1, 7\]

There are no better solutions and the answer is by using \(2\) terms.