给定一个整数值 $$$x$$$ 和一个字符串 $$$s$$$,其中包含从 $$$1$$$ 到 $$$9$$$ 的数字。
字符串的子字符串是该字符串的连续子序列。
令 $$$f(l, r)$$$ 为子串 $$$s[l..r]$$$ 的数字之和。
让我们调用子字符串 $$$s[l_1..r_1]$$$ $$$x$$$-prime if
- $$$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$$$ 素数子字符串?如果给定字符串 $$$s$$$ 中不存在 $$$x$$$ 素数子字符串,则打印 $$$0$$$。
输入
第一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 1000$$$)。 $$$s$$$ 仅包含从 $$$1$$$ 到 $$$9$$$ 的数字(含)。
第二行包含一个整数 $$$x$$$ ($$$1 \le x \le 20$$$)。
输出
打印单个整数 - 应从字符串中删除的最小字符数,以便其中不存在 $$$x$$$ 素数子字符串。如果给定字符串 $$$s$$$ 中不存在 $$$x$$$ 素数子字符串,则打印 $$$0$$$。
示例
输入 #1
116285317 8
输出 #1
2
输入 #2
314159265359 1
输出 #2
2
输入 #3
13 13
输出 #3
0
输入#4
3434343434 7
输出#4
5
注意
在第一个示例中,有两个 $$$8$$$ 素数子字符串“8”和“53”。您可以擦除这些字符以删除这两个字符:“116285317”。生成的字符串“1162317”不包含 $$$8$$$ 素数子字符串。删除这些字符也是一个有效的答案:“116285317”。
在第二个示例中,您只需删除两个即可。
在第三个示例中,没有 $$$13$$$-素数子字符串。根本不存在数字总和等于 $$$13$$$ 的子字符串。
在第四个示例中,字符串中既不能包含“34”,也不能包含“43”。因此,你必须要么全部删除,要么全部删除。每个都有$$$5$$$,所以哪个并不重要。