特工 John 掌握了一些绝密信息，这些信息被编码为一个数字 $N$。为了避免向第三方泄露信息，他用古 Byteotian 语写下了 $N$ 在 $b$ 进制下的各位数字。（这种语言中的每个数字都由一串小写拉丁字母表示。）他用零个或多个随机字母将这些数字隔开（这些随机字母不会出现在表示数字的单词内部，只会出现在开头、结尾或两个相邻数字之间）。已知 Byteotian 人不使用零，因此他们的语言中没有表示零的单词。幸运的是，该数字的表示中不包含零。

遗憾的是，以这种方式编码的信息可能会产生歧义。

给定编码后的信息，请找出可能被编码出的最大数字 $N$。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述。

每个测试用例的描述以一行包含进制数 $b$ ($3 \le b \le 5 \cdot 10^4$) 开始。 随后有 $(b - 1)$ 行，每行包含一个非空的小写字母字符串。其中第 $i$ 行是古 Byteotian 语中表示数字 $i$ 的单词。这些单词均非空且互不相同。所有这些单词的长度总和不超过 $5 \cdot 10^5$。

测试用例描述的最后一行包含特工 John 的编码信息。其长度不超过 $3 \cdot 10^5$。

输出格式

按输入顺序输出每个测试用例的答案。对于每个测试用例，输出一行，包含用空格分隔的数字序列。如果没有任何数字符合该加密信息，则在该行输出一个数字 0。

样例

输入 1

1
10
one
two
three
four
five
six
seven
eight
nine
twohundredsixtynine

输出 1

2 6 9