问题 K: String

Alice and Bob are playing a string game.

Alice has a string $S$, Bob has a string $T$, in each round of the game, Bob will choose a string interval $T[l,r]$ in $T$ , Alice needs to find a string interval �[�′,�′]S[l′,r′] in $S$ to make $T[l,r]$ is a substring of �[�′,�′]S[l′,r′].

We define an interval of pairs $[l,r]$string $S$ if and only if 1≤�≤�≤����1≤l≤r≤Slen(����Slen is the string $S$ length), all optional intervals of a string are all $l,r$ that satisfy the condition. $S[l,r]$ is a string formed by concatenating the $S$ string from the $l$th character to the $r$th character in order.

A string $T$ is a substring of the string $S$ if and only if the string $T$ can be obtained by removing some characters from the beginning and the end of the string $S$ (or not).

Both Alice and Bob find this game too boring, and they want to know if Bob randomly chooses one of all the intervals in the string $T$, how many intervals Alice can choose from the string $S$ and such that the string selected by Bob is a substring of the string selected by Alice.

The game will be played multiple times, and in each round, Bob will change the string $T$, so you will need to answer multiple sets of questions.

For the first line,input a positive integer $T(1\le T\le 5)$, representing the total number of test data.

For each test data,the first line contains two positive integers $n,q(1\le n,q\le 100000)$, which represent the length of the string and the number of queries.

The second line contains a string of length $n$ representing the $S$ string owned by Alice.

The next $q$ lines, each line contains a string, representing the query string $T$.

It is guarantees that the length of all query strings does not exceed 106106 in one test.

It is guaranteed that the input string contains only English lowercase letters.

1
4 4
aaba
a
aa
ab
cab

9
7
332748124
166374062