A13727 | x-prime Substrings

You are given an integer value $x$ and a string $s$ consisting of digits from $1$ to $9$ inclusive.

A substring of a string is a contiguous subsequence of that string.

Let $f(l, r)$ be the sum of digits of a substring $s[l..r]$ .

Let's call substring $s[l_1..r_1]$ $x$ -prime if

- $f(l_1, r_1) = x$ ;
- there are no values $l_2, r_2$ such that
- $l_1 \le l_2 \le r_2 \le r_1$ ;
- $f(l_2, r_2) \neq x$ ;
- $x$ is divisible by $f(l_2, r_2)$ .

You are allowed to erase some characters from the string. If you erase a character, the two resulting parts of the string are concatenated without changing their order.

What is the minimum number of characters you should erase from the string so that there are no $x$ -prime substrings in it? If there are no $x$ -prime substrings in the given string $s$ , then print $0$ .

The first line contains a string $s$ ( $1 \le |s| \le 1000$ ). $s$ contains only digits from $1$ to $9$ inclusive.

The second line contains an integer $x$ ( $1 \le x \le 20$ ).

Print a single integer — the minimum number of characters you should erase from the string so that there are no $x$ -prime substrings in it. If there are no $x$ -prime substrings in the given string $s$ , then print $0$ .