Description

Little Q is now checking whether string $A$ matches $B$. Two strings are considered matched if they have the same length, and there is no position $i$ that $A_i$ is different from $B_i$.

However, Little Q is a kind man, he forgives every person who hurt him. What's more, he even forgives strings! He gives the string $k$ opportunities, if there are no more than $k$ positions $i$ that $A_i$ is different from $B_i$, then Little Q will also consider the two strings matched. Note that both of the strings may contain the wildcard character '$\texttt{*}$', which can match exactly one any character, in such a case this pair won't consume the forgiveness opportunities.

Let's denote $occ(S,T)$ as the number of substrings in string $S$ which matches $T$, two substrings are considered different if they start in different places. You will be given two strings $S$ and $T$, write a program to compute the value of $occ(S,T)$ for $k=0,1,2,\dots,|T|$.

Format

Input

The first line contains a single integer $K$ ($1 \leq K \leq 100$), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $m$ ($1 \leq m\leq n \leq 200\,000$), denoting the length of $S$ and the length of $T$.

The second line contains a string $S$ of length $n$.

The third line contains a string $T$ of length $m$.

It is guaranteed that the sum of all $n$ is at most $1\,000\,000$. Both $S$ and $T$ can only contain the characters in $\{$'$\texttt{0}$', '$\texttt{1}$', '$\texttt{2}$', '$\texttt{3}$', '$\texttt{4}$', '$\texttt{5}$', '$\texttt{6}$', '$\texttt{7}$', '$\texttt{8}$', '$\texttt{9}$', '$\texttt{*}$'$\}$.

Output

For each test case, output $m+1$ lines, the $i$-th ($1\leq i\leq m+1$) of which containing an integer, denoting the value of $occ(S,T)$ when $k=i-1$.

Samples

1
5 3
012*4
1*3

1
1
3
3