>time limit per test2 seconds

memory limit per test

512 megabytes

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?

Input

The only line of the input contains two integers $$$n$$$ and $$$x$$$ ($$$2 \le n \le 19$$$; $$$1 \le x \lt 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.

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

18:["dp","hashing","shortest paths"] 17:{"tags":"$18","ratingMin":null,"ratingMax":null,"q":"","order":"BY_ID_DESC","page":1,"showTags":true,"hideSolved":false,"platform":"codeforces"}

Problemset