题目描述

给定一个文本 $t$ 和一个包含 $n$ 个字符串 $s_1,s_2,…,s_n$ 的集合。

每一步，您可以在文本 $t$ 中选择任何一段等于 $s_i$ 的子串，并将文本的相应字符涂成红色。例如，如果 $t = bababa，s_1 = ba，s_2 = aba$，则可以在一步中获得 $t =$bababa，$t =$bababa 或 $t =$bababa。

您想将文本 $t$ 的所有字母都涂成红色。反复涂同一段时，它将保持为红色。

在上面的示例中，三个步骤就足够了：

• 让我们将 $t[2…4] = s_2 = aba$ 涂成红色，我们得到 $t =$bababa。
• 让我们将 $t[1…2] = s_1 = ba$ 涂成红色，我们得到 $t =$bababa。
• 让我们将 $t [4…6] = s_2 = aba$ 涂成红色，我们得到 $t =$bababa。

每个字符串 $s_i$ 可以应用任意次数（或不应用）。染色出现可以任意交叉。

确定涂色所有文本 $t$ 的最小步骤数以及如何实现它。如果无法将文本 $t$ 的所有字母涂成红色，则输出 -1。

输入格式

输入的第一行包含一个整数 $q (1≤q≤100)$ — 测试中的测试用例数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个文本 $t (1≤|t|≤100)$，只包含小写拉丁字母，其中 $|t|$ 是文本 $t$ 的长度。

每个测试用例的第二行包含一个单独的整数 $n(1≤n≤10)$ — 集合中字符串的数量。

接下来是 $n$ 行，每行包含一个字符串 $s_i(1≤|s_i|≤10)$，只包含小写拉丁字母，其中 $|s_i|$ 是字符串 $s_i$ 的长度。

输出格式

对于每个测试用例，请在单独的行上打印答案。

如果无法将文本的所有字母染成红色，则打印包含数字-1 的单行。

否则，在第一行上打印数字 $m$ ——将所有字母 $t$ 都染成红色所需的最小步数。

然后在接下来的 $m$ 行中打印索引对: $w_j$ 和 $p_j(1≤j≤m)$，它们表示使用索引 $w_j$ 的字符串作为子字符串来覆盖文本 $t$ 中从位置 $p_j$ 开始的一段。可以以任何顺序输出这些对。

如果有多个答案，请输出其中任何一个。

测试样例

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

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

样例说明

在问题陈述中已经解释了第一个测试用例。

在第二个测试用例中，无法将文本的所有字母都染成红色。