G. Nearest Strings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Define $$$d(a,b)$$$ — distance between two strings $$$a$$$ and $$$b$$$ as the number of single-character insertions and deletions needed to transform one string to another.

You are given a list of $$$n$$$ pairwise distinct strings $$$s_1, \dots, s_n$$$ consisting of only lowercase Latin letters. For every string, find the nearest string to it from the same list. That is, for every $$$i$$$, find such $$$j$$$ that $$$j \ne i$$$ and $$$d(s_i, s_j)$$$ is the smallest possible. If there are multiple strings with the same distance, pick the lexicographically smallest one.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$ 2 \le n \le 2 \cdot 10^4$$$) — the number of strings.

Then $$$n$$$ lines follow, containing strings $$$s_1, \dots, s_n$$$ consisting of only lowercase Latin letters, $$$1 \le |s_i| \le 8$$$. It is guaranteed that the strings are pairwise distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^4$$$.

Output

For each test case, print two lines of $$$n$$$ integers, separated by spaces.

On the first line, print numbers $$$a_1, \dots, a_n$$$, where $$$a_i$$$ is the index of the nearest string to $$$s_i$$$ ($$$1 \le a_i \le n, a_i \ne i$$$).

On the second line, print the corresponding smallest distances: $$$d(s_1, s_{a_1}), \dots d(s_n, s_{a_n})$$$.

Example
Input
3
2
abc
abd
6
abcde
abcd
abcfe
bcde
bcfe
aaaaa
4
codeforc
code
forces
polygon
Output
2 1 
2 2 
2 1 5 1 3 2 
1 1 1 1 1 7 
2 1 2 2 
4 4 6 9
Note

Note that the definition of distance in this problem is different from the standard "edit distance" definition, as it doesn't allow replacements.