三进制字符串是由数字 0、1 或 2 组成的序列。

对于一个三进制字符串，Chiaki 可以执行以下任意操作：

• 将一个 00 替换为 12，或反之。例如，120011 可以变为 121211 或 000011。
• 将一个 111 替换为 20，或反之。例如，1112011 可以变为 202011 或 11111111。
• 移除一个 22，或在任意位置插入字符串 22（也可以插入在字符串的开头或结尾）。例如，1221 可以变为 11、221221、122221 或 122122。
• 移除一个 012，或在任意位置插入字符串 012（也可以插入在字符串的开头或结尾）。例如，10121 可以变为 11、01210121、10120121、10012121、10101221、10120121 或 10121012。

Chiaki 有一个长度为 $n$ 的三进制字符串 $s$ 和 $m$ 个其他三进制字符串 $t_1, t_2, \dots, t_m$。对于每个三进制字符串 $t_i$，她想知道有多少对 $(l, r)$ ($1 \le l \le r \le n$) 满足子串 $s_{l \dots r}$ 在执行上述若干操作后可以变为 $t_i$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^6$)，分别表示字符串 $s$ 的长度和其它三进制字符串的数量。

第二行包含一个长度为 $n$ 的三进制字符串 $s$。

接下来的 $m$ 行，每行包含一个三进制字符串 $t_i$ ($1 \le |t_i| \le 10^6$)。

保证所有测试数据中字符串长度之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出 $m$ 行，其中第 $i$ 行包含一个整数，表示字符串 $t_i$ 的答案。

样例

输入 1

2
11 4
01021001020
0
1
2
012
6 3
012210
0
1
2

输出 1

6
3
4
0
2
4
4