F. x-простые подстроки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$x$$$ и строка $$$s$$$, состоящая из цифр от $$$1$$$ до $$$9$$$ включительно.

Подстрокой строки называется последовательная подпоследовательность этой строки.

Пусть $$$f(l, r)$$$ будет равно сумме цифр в подстроке $$$s[l..r]$$$.

Назовем подстроку $$$s[l_1..r_1]$$$ $$$x$$$-простой, если

  • $$$f(l_1, r_1) = x$$$;
  • не существует таких значений $$$l_2, r_2$$$, что
    • $$$l_1 \le l_2 \le r_2 \le r_1$$$;
    • $$$f(l_2, r_2) \neq x$$$;
    • $$$x$$$ делится на $$$f(l_2, r_2)$$$.

Разрешено удалять любые символы из строки. Если вы удаляете символ, то две полученные части строки склеиваются, не меняя порядок.

Какое минимальное количество символов надо удалить из строки, чтобы она не содержала $$$x$$$-простых подстрок? Если $$$x$$$-простых подстрок нет в данной строке $$$s$$$, то выведите $$$0$$$.

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

В первой строке записана строка $$$s$$$ ($$$1 \le |s| \le 1000$$$). $$$s$$$ содержит только цифры от $$$1$$$ до $$$9$$$ включительно.

Во второй строке записано одно целое число $$$x$$$ ($$$1 \le x \le 20$$$).

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

Выведите одно целое число — минимальное количество символов, которые надо удалить из строки, чтобы она не содержала $$$x$$$-простых подстрок? Если $$$x$$$-простых подстрок нет в данной строке $$$s$$$, то выведите $$$0$$$.

Примеры
Входные данные
116285317
8
Выходные данные
2
Входные данные
314159265359
1
Выходные данные
2
Входные данные
13
13
Выходные данные
0
Входные данные
3434343434
7
Выходные данные
5
Примечание

В первом примере в строке две $$$8$$$-простых подстроки «8» и «53». Можно удалить данные символы, чтобы избавиться от обеих: «116285317». Полученная строка «1162317» не содержит $$$8$$$-простых подстрок. Также можно удалить такие символы: «116285317».

Во втором примере необходимо просто удалить обе единицы.

В третьем примере нет $$$13$$$-простых подстрок. В нем вообще нет подстрок с суммой цифр равной $$$13$$$.

В четвертом примере в строке не должно быть ни «34», ни «43». Поэтому необходимо удалить либо все тройки, либо все четверки. Их по $$$5$$$ штук, поэтому можно удалить любые из них.