说明

何为字符串匹配, 我就不多说了.
but, 这里的匹配, 你可以打乱字符顺序.
也就是说主串为"abcba", 你可以匹配到子串"abc"2次, 分别对应主串里的[0, 2]:"abc"和[2, 4]:"cba".
so, 赶紧来ac此题吧.

输入格式

多组数据, 最开始给出1个正整数T, 代表数据组数.
每组数据的格式如下:

1个字符串, 代表主串.1个正整数Q, 代表询问个数.Q行输入:

1个字符串, 代表要查询的子串.

所有给出的字符串都由小写字母构成.

输出格式

对于每个询问, 输出1行:

1个数字, 代表这个询问的子串在主串中出现的次数.

样例

1
abcbacabccabacbcbcacb
6
abc
cca
ccb
ccc
aac
ccb

10
2
3
0
1
3

提示

T <= 20.

Q <= 1000.

主串长度 <= 1000.

子串长度 <= 10.