#104786. [BZOJ 4786] [Zjoi2017]多项式

九条可怜最近研究了一下多项式在系数模 意义下的性质。她发现可以用多项式在模 意义下的乘法得到一个很长的字符串：

对于一个 次的系数为 或 的多项式 ，我们在模 意义下计算 ，则

为一个 次的多项式，它有 个系数，将这些系数从高位到低位写下来，就可以得到一个长度为 的 字符串。

例如对于多项式 ，计算 ，这样我们得到了一个长度为 的字符串 。

现在可怜有一个次数为 的多项式 ，整数 以及一个长度为 的 01 串 。令 为 得到的字符串， 为 的第 个字符到第 个字符，可怜想要知道 在 中出现了多少次。

第一行输入一个整数 表示数据组数。
每组数据第一行输入五个整数 。
第二行输入一个长度为 的 01 串表示多项式 的系数，其中第 位表示 的第 次系数。
第三行输入一个长度为 的字符串表示字符串 。

对于每组数据输出一个整数表示答案。

样例输入 #1

1
3 3 2 1 10
1011
01

样例输出 #1

2

样例输入 #2

4
18 425979 3 4394755 5294599
1110011000110000001
101
18 654615 18 8371190 8974716
1110110011000010001
100011111010101011
18 509662 18 525987 5910726
1000010010001100000
010100000101010100
18 446204 18 2628281 3483268
1011011111101001001
000000000100010001

样例输出 #2

84292
1367
1068
6713

对于 的数据，，。