23490번 - Ternary String Revolution 다국어

문제

A ternary string is a sequence of digits, where each digit is either 0ドル,ドル 1ドル,ドル or 2ドル$.

For a ternary string, Chiaki can perform any of the following operations:

• Replace one occurrence of 00ドル$ to 12ドル$ or vice versa. For example, 120011ドル$ can change to 121211ドル$ or 000011ドル$.
• Replace one occurrence of 111ドル$ to 20ドル$ or vice versa. For example, 1112011ドル$ can change to 202011ドル$ or 11111111ドル$.
• Remove one occurrence of 22ドル$ or put string 22ドル$ on any position (you can also put it at the beginning or the ending of the string). For example, 1221ドル$ can change to 11ドル,ドル 221221ドル,ドル 122221ドル$ or 122122ドル$.
• Remove one occurrence of 012ドル$ or put string 012ドル$ on any position (you can also put it at the beginning or the ending of the string). For example, 10121ドル$ can change to 11ドル,ドル 01210121ドル,ドル 10120121ドル,ドル 10012121ドル,ドル 10101221ドル,ドル 10120121ドル$ or 10121012ドル$.

Chiaki has a ternary string $s$ of length $n$ and $m$ other ternary strings $t_1,t_2,\dots,t_m$. For each ternary string $t_i,ドル she would like to know the number of pairs $(l, r)$ (1ドル \le l \le r \le n$) such that the substring $s_{l..r}$ can become $t_i$ after performing several above operations.

입력

There are multiple test cases. The first line of input contains an integer $T,ドル indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ (1ドル \le n, m \le 10^6$) -- the length of $s$ and the number of other ternary strings.

The second line contains a ternary string $s$ of length $n$.

Each of the next $m$ lines contains a ternary string $t_i$ (1ドル \le |t_i| \le 10^6$).

It is guaranteed that the sum of the length of all strings over all test cases does not exceed 2ドル \times 10^6$.

출력

For each test cases, output $m$ lines, where the $i$-th line contains an integer denoting the answer for ternary string $t_i$.

제한

힌트