A15139. Required Length

You are given two integer numbers, $n$ and $x$ . You may perform several operations with the integer $x$ .

Each operation you perform is the following one: choose any digit $y$ that occurs in the decimal representation of $x$ at least once, and replace $x$ by $x \cdot y$ .

You want to make the length of decimal representation of $x$ (without leading zeroes) equal to $n$ . What is the minimum number of operations required to do that?

The only line of the input contains two integers $n$ and $x$ ( $2 \le n \le 19$ ; $1 \le x < 10^{n-1}$ ).

Print one integer — the minimum number of operations required to make the length of decimal representation of $x$ (without leading zeroes) equal to $n$ , or $-1$ if it is impossible.

In the second example, the following sequence of operations achieves the goal:

1. multiply $x$ by $2$ , so $x = 2 \cdot 2 = 4$ ;
2. multiply $x$ by $4$ , so $x = 4 \cdot 4 = 16$ ;
3. multiply $x$ by $6$ , so $x = 16 \cdot 6 = 96$ ;
4. multiply $x$ by $9$ , so $x = 96 \cdot 9 = 864$ .