## CBOJ Exec Selection Contest Problem 2 - Pretty Sequence

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

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$$.

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

$$1 \le V \le 20$$

$$1 \le V \le 100$$

$$1 \le V \le 1\,000$$

16

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.

8

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.