D. Color with Occurrences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given some text $$$t$$$ and a set of $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$.

In one step, you can choose any occurrence of any string $$$s_i$$$ in the text $$$t$$$ and color the corresponding characters of the text in red. For example, if $$$t=\texttt{bababa}$$$ and $$$s_1=\texttt{ba}$$$, $$$s_2=\texttt{aba}$$$, you can get $$$t=\color{red}{\texttt{ba}}\texttt{baba}$$$, $$$t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$$$ or $$$t=\texttt{bab}\color{red}{\texttt{aba}}$$$ in one step.

You want to color all the letters of the text $$$t$$$ in red. When you color a letter in red again, it stays red.

In the example above, three steps are enough:

  • Let's color $$$t[2 \dots 4]=s_2=\texttt{aba}$$$ in red, we get $$$t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$$$;
  • Let's color $$$t[1 \dots 2]=s_1=\texttt{ba}$$$ in red, we get $$$t=\color{red}{\texttt{baba}}\texttt{ba}$$$;
  • Let's color $$$t[4 \dots 6]=s_2=\texttt{aba}$$$ in red, we get $$$t=\color{red}{\texttt{bababa}}$$$.

Each string $$$s_i$$$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.

Determine the minimum number of steps needed to color all letters $$$t$$$ in red and how to do it. If it is impossible to color all letters of the text $$$t$$$ in red, output -1.

Input

The first line of the input contains an integer $$$q$$$ ($$$1 \le q \le 100$$$) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains the text $$$t$$$ ($$$1 \le |t| \le 100$$$), consisting only of lowercase Latin letters, where $$$|t|$$$ is the length of the text $$$t$$$.

The second line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10$$$) — the number of strings in the set.

This is followed by $$$n$$$ lines, each containing a string $$$s_i$$$ ($$$1 \le |s_i| \le 10$$$) consisting only of lowercase Latin letters, where $$$|s_i|$$$ — the length of string $$$s_i$$$.

Output

For each test case, print the answer on a separate line.

If it is impossible to color all the letters of the text in red, print a single line containing the number -1.

Otherwise, on the first line, print the number $$$m$$$ — the minimum number of steps it will take to turn all the letters $$$t$$$ red.

Then in the next $$$m$$$ lines print pairs of indices: $$$w_j$$$ and $$$p_j$$$ ($$$1 \le j \le m$$$), which denote that the string with index $$$w_j$$$ was used as a substring to cover the occurrences starting in the text $$$t$$$ from position $$$p_j$$$. The pairs can be output in any order.

If there are several answers, output any of them.

Example
Input
6
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb
Output
3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13
Note

The first test case is explained in the problem statement.

In the second test case, it is impossible to color all the letters of the text in red.