D. Требуемая длина
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых числа, $$$n$$$ и $$$x$$$. Вы можете провести несколько операций с числом $$$x$$$.

Каждая операция заключается в следующем: выбрать любую цифру $$$y$$$, которая встречается в десятичной записи $$$x$$$ хотя бы один раз, и заменить значение $$$x$$$ на $$$x \cdot y$$$.

Вы должны сделать так, чтобы длина десятичной записи $$$x$$$ (без ведущих нулей) стала равна $$$n$$$. Какое минимальное количество операций вам потребуется для этого?

Входные данные

В единственной строке заданы два целых числа $$$n$$$ и $$$x$$$ ($$$2 \le n \le 19$$$; $$$1 \le x < 10^{n-1}$$$).

Выходные данные

Выведите одно целое число — минимальное количество операций, необходимое, чтобы сделать длину десятичной записи $$$x$$$ (без ведущих нулей) равной $$$n$$$, или $$$-1$$$, если это невозможно.

Примеры
Входные данные
2 1
Выходные данные
-1
Входные данные
3 2
Выходные данные
4
Входные данные
13 42
Выходные данные
12
Примечание

Во втором примере следующая последовательность операций позволяет достичь цели:

  1. умножить $$$x$$$ на $$$2$$$, тогда $$$x = 2 \cdot 2 = 4$$$;
  2. умножить $$$x$$$ на $$$4$$$, тогда $$$x = 4 \cdot 4 = 16$$$;
  3. умножить $$$x$$$ на $$$6$$$, тогда $$$x = 16 \cdot 6 = 96$$$;
  4. умножить $$$x$$$ на $$$9$$$, тогда $$$x = 96 \cdot 9 = 864$$$.