I. Two Operations
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Your math teacher, Agrippina Sergeevna, wrote the number $$$1$$$ on the board. The task for today's class is to obtain the number $$$N$$$ from it. Of course, your actions are limited to a certain set of possible operations. All you can do is:

  • double the number written on the board;
  • rearrange the digits of the number in any order (the new number should not start with zero).

Everyone wants to go home as soon as possible, so it would be nice to obtain the number $$$N$$$ with the minimum number of operations. Help the class (and yourself) by finding the minimum number of described operations required to obtain the number $$$N$$$, or determine that it is impossible, in which case everyone will have to stay until the end of the class.

Input

The input consists of a single line containing an integer $$$N$$$ that needs to be obtained ($$$1 \leqslant N \leqslant 9999$$$).

Output

Output a single integer — the minimum number of operations required to obtain $$$N$$$, or "-1" if it is impossible.

Examples
Input
4
Output
2
Input
61
Output
5
Input
3
Output
-1
Note

In the first example, the following sequence of actions will work: $$$1 \to 2 \to 4$$$.

In the second example, you can proceed as follows: $$$1 \to 2 \to 4 \to 8 \to 16 \to 61$$$.