Дано целое число \(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\).
Выходные данные
Выведите одно целое число — минимальное количество символов, которые надо удалить из строки, чтобы она не содержала \(x\)-простых подстрок? Если \(x\)-простых подстрок нет в данной строке \(s\), то выведите \(0\).
Примечание
В первом примере в строке две \(8\)-простых подстроки «8» и «53». Можно удалить данные символы, чтобы избавиться от обеих: «116285317». Полученная строка «1162317» не содержит \(8\)-простых подстрок. Также можно удалить такие символы: «116285317».
Во втором примере необходимо просто удалить обе единицы.
В третьем примере нет \(13\)-простых подстрок. В нем вообще нет подстрок с суммой цифр равной \(13\).
В четвертом примере в строке не должно быть ни «34», ни «43». Поэтому необходимо удалить либо все тройки, либо все четверки. Их по \(5\) штук, поэтому можно удалить любые из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
116285317
8
|
2
|
|
2
|
314159265359
1
|
2
|
|
3
|
13
13
|
0
|
|
4
|
3434343434
7
|
5
|