暂无测试数据。

题目

《禁忌法典》是一本记载了所有魔法的究极魔导书，从简单的入门魔法，到究极的恐怖魔法都是可以在里面解读并使用出来的。

这本魔导书的使用方法很特别，魔导书可以看成是n个字母（26个小写字母）组成的一个长字符串，所有的字母全部连在一起组成了这本书。每个字母在书中对应了一个魔力值，a为1，b为2，c为3以此类推。

从书中任意截取一段连续字母可以组成一串咒语，而咒语的协和度等于咒语内所有字母的魔力值总和。例如一段咒语是aabc，他的协和度为 1 + 1 + 2 + 3 = 7

在法典中，并不是所有的魔法都是可以使用的，要想使用魔法，首先必须将自己的魔法属性切换成p属性，p用一个普通的正整数（2 <= p <= 100）表示，当一串咒语的协和度刚好能被p整除时，那么在当前法力属性下，这就是一个可用的魔法。

例如一段文字中akdfireballtd可以截取出一段咒语fireball（必须连续），其协和值为6 + 9 + 18 + 5 + 2 + 1 + 12 + 12 = 65，如果此时的p为5，由于65能被5整除，所以你可以使用该魔法，但是如果你此时的p为7，由于65不能被7整除，所以就不能释放。

现在给你这本法典的所有内容和你当前的法力属性p，你能计算出在当前法力属性为p时，这本法典中有多少魔法可以使用吗？

格式

输入格式

首先是一个正整数t（1 <= t <= 10）代表数据组数
每组数据开头是一个字符串S，表示法典的所有内容（1 <= |S| <= 1000）
接着是一个正整数p（2 <= p <= 100），表示当前的魔法属性

输出格式

每组数据输出一行，每行一个正整数，即在当前法力属性下能使用法典内多少魔法？由于魔法的总量可能很大，你只需要输出答案对23333取余的结果即可。

样例 1

输入样例

1
abfcgd
3

输出样例

7

限制

1s, 1024KiB for each test case.

提示

解释下样例，由于你此时的p为3，你可以取出魔法abf（协和度为 1+2+6 = 9，能被3整除）或者 bfcg（协和度也能被3整除）等等来使用，在本样例中，事实上一共有7种可以使用的魔法。