삼진 문자열 혁명

삼진 문자열은 각 자리가 $0$, $1$, $2$ 중 하나인 문자열이다.

삼진 문자열에 대해 Chiaki는 다음 연산을 원하는 만큼 수행할 수 있다.

• $00$ 한 곳을 $12$로 바꾸거나, $12$ 한 곳을 $00$으로 바꾼다. 예를 들어 $120011$은 $121211$이나 $000011$로 바뀔 수 있다.
• $111$ 한 곳을 $20$으로 바꾸거나, $20$ 한 곳을 $111$로 바꾼다. 예를 들어 $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$에 대해, 부분 문자열 $s_{l..r}$에 위 연산을 여러 번 수행해 $t_i$로 만들 수 있는 쌍 $(l, r)$ ($1 \le l \le r \le n$)의 개수를 구하려고 한다.

여러 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 10^6$)이 주어진다. $n$은 $s$의 길이이고, $m$은 다른 삼진 문자열의 개수이다.

둘째 줄에는 길이 $n$인 삼진 문자열 $s$가 주어진다.

다음 $m$개 줄에는 각각 삼진 문자열 $t_i$ ($1 \le |t_i| \le 10^6$)가 주어진다.

모든 테스트 케이스에 걸친 모든 문자열 길이의 합은 $2 \times 10^6$을 넘지 않는다.

각 테스트 케이스마다 $m$개 줄을 출력한다. $i$번째 줄에는 삼진 문자열 $t_i$에 대한 답을 나타내는 정수를 출력한다.