Даны два целых числа, \(n\) и \(x\). Вы можете провести несколько операций с числом \(x\).
Каждая операция заключается в следующем: выбрать любую цифру \(y\), которая встречается в десятичной записи \(x\) хотя бы один раз, и заменить значение \(x\) на \(x \cdot y\).
Вы должны сделать так, чтобы длина десятичной записи \(x\) (без ведущих нулей) стала равна \(n\). Какое минимальное количество операций вам потребуется для этого?
Выходные данные
Выведите одно целое число — минимальное количество операций, необходимое, чтобы сделать длину десятичной записи \(x\) (без ведущих нулей) равной \(n\), или \(-1\), если это невозможно.
Примечание
Во втором примере следующая последовательность операций позволяет достичь цели:
- умножить \(x\) на \(2\), тогда \(x = 2 \cdot 2 = 4\);
- умножить \(x\) на \(4\), тогда \(x = 4 \cdot 4 = 16\);
- умножить \(x\) на \(6\), тогда \(x = 16 \cdot 6 = 96\);
- умножить \(x\) на \(9\), тогда \(x = 96 \cdot 9 = 864\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
|
-1
|
|
2
|
3 2
|
4
|
|
3
|
13 42
|
12
|