If there exists an integer $k$ such that string $S$ becomes equal to string $T$ after being cyclically right-shifted by $k$ positions, then the strings $S$ and $T$ are said to be cyclically right-shifted.

Now, given $n$ strings of length $m$ consisting of lowercase letters, there are a total of $Q$ queries. Each query provides two positive integers $x$ and $y$. If the strings $s_x$ and $s_y$ are cyclically right-shifted, output Yes; otherwise, output No.

Input

The input consists of multiple test cases. The first line contains a single integer $T$($1 \le T \le 5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^5$) — the number of the strings and the length of strings.

Each of the next $n$ lines contains a string of lowercase letters $s_i$.

The next line contains a positive integer $Q$ ($1 \le Q \le 10^5$).

Each of the next $Q$ lines contains two integers $x$, $y$ ($1 \le x, y \le n$) asks whether the string $s_x$ and the string $s_y$ are cyclic isomorphic.

Output

For each test case, output $Q$ lines. Each line should contain a string indicating whether the current query strings $s_x$ and $s_y$ are cyclically isomorphic. If they are cyclically isomorphic, output Yes; otherwise, output 'No'.

Example

2
2 2
ab
ba
1
1 2
4 3
aab
baa
bba
bab
6
1 2
1 3
1 4
2 3
2 4
3 4

Yes
Yes
No
No
No
No
Yes

Limitation

Time limit: 2 seconds

Memory limit: 512 megabytes