x-prime 子串

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定整数 $x$ 和一个只含数字 $1$ 到 $9$ 的字符串 $s$。记子串的数字和为 $f(l,r)$。

一个子串称为 $x$-prime，当且仅当它的数字和等于 $x$，并且它内部不存在另一个数字和不等于 $x$、但其数字和能整除 $x$ 的非空子串。

你可以删除若干字符，剩余字符保持原相对顺序并拼接。求至少删除多少个字符，才能使所得字符串中不存在 $x$-prime 子串。

输入格式

第一行输入字符串 $s$。

第二行输入整数 $x$。

输出格式

输出最少删除字符数。

样例输入 1

116285317
8

样例输出 1

2

样例输入 2

314159265359
1

样例输出 2

2

样例输入 3

13
13

样例输出 3

0

样例输入 4

3434343434
7

样例输出 4

5

数据范围

$1\le \lvert s\rvert\le1000$，$s$ 只含数字 $1$ 到 $9$；$1\le x\le20$。