String

Problem Description

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\leq l\leq r\leq S_{len}$($S_{len}$ 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.

Input

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\leq n,q\leq 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 $10^6$ in one test. It is guaranteed that the input string contains only English lowercase letters.

Output

For each query, output a line with a positive integer representing the expected number, and the answer modulo $998244353$.

Sample Input

1
4 4
aaba
a
aa
ab
cab

Sample Output

9
7
332748124
166374062

Hint

For the third query, $Bob$ can choose from three intervals of $[1,1][2,2][1,2]$, and the corresponding $Alice$ has $9,6,4$ intervals to choose from, So the answer is $\frac{9+6+4}{3}$

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）