Problem Description

You are given $N$ strings.Their total length is $L$.

There are $Q$ questions.

For each question please work out two tasks:

①whether $S_x$ is a subsequence of $S_y$.

②whether $S_x$ is a substring of $S_y$.

If the statement is true print $1$,otherwise print $0$

Input

In the first line there is the testcase $T$.

For each teatcase:

In the first line there are two numbers $N$ and $Q$.

In the next $N$ lines there are $N$ strings $i$-th line is a string standing for $S_i$.

**Note that $S_i$ consists of only lower alphabets.**

In the last $Q$ lines there are two numbers$ (x,y)$.

$T \leq 5$。$N,L,Q \leq 100000$。Every string's length is at least $1$。

There are $60\%$ testcases that $L \leq 100$，$Q \leq 1000$。

You'd better print the enter in the last line when you hack others.

You'd better not print space in the last of each line when you hack others.

Output

For each testcase,print only one lines.

It's a string contains only $0$ and $1$ and its length is $Q*2$.

$i*2-1$-th character is the answer of the $i$-th question of ①，

and $i*2$-th character is the answer of the $i$-th question of ②。

1
6 6
orz
stilwell
skydec
se
dec
orz
1 2
1 3
1 6
4 1
4 2
6 1

000011001011