#P1681D. Required Length
-
ID: 1131
Type: RemoteJudge
2000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: 5
Uploaded By:
Hydro
Tags> Required Length
Description
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.
Input
The only line of the input contains two integers $n$ and $x$ ($2 \le n \le 19$; $1 \le x < 10^{n-1}$).
Output
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.
2 1
3 2
13 42
-1
4
12
Note
In the second example, the following sequence of operations achieves the goal:
- multiply $x$ by $2$, so $x = 2 \cdot 2 = 4$;
- multiply $x$ by $4$, so $x = 4 \cdot 4 = 16$;
- multiply $x$ by $6$, so $x = 16 \cdot 6 = 96$;
- multiply $x$ by $9$, so $x = 96 \cdot 9 = 864$.