H. Hotkeys
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As an experienced programming competition organizer, Heinz knows a lot about bugs in related systems. That is why he decided to make a new tool for creating programming problems, Hyperbola v0.01!

One of the frequent menus in Hyperbola v0.01 contains several items. It is very important to make sure users can navigate through that menu using single key presses. Therefore, for each item of the menu, Heinz wants to pick a distinct character contained in the name (its hotkey), so that pressing that key would invoke the corresponding item.

Heinz only values lowercase English letters and digits, so for the purpose of the algorithm he preemptively converted all uppercase English letters to lower case and removed all other possible characters from names.

Suppose that we pick the $$$p_i$$$-th character of the $$$i$$$-th item as a hotkey. Heinz wants to minimize the sum of $$$p_i$$$. Find such an arrangement of hotkeys, or report that this is impossible.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The first line of a test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 30$$$).

The next $$$n$$$ lines contain strings $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq |s_i| \leq 10^5$$$) of lowercase English letters and digits, denoting the menu items. It is guaranteed that the sum of $$$|s_i|$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print NO if it is impossible to assign pairwise distinct hotkeys. Otherwise, print YES, and in the next line, print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq |s_i|$$$): the positions of the chosen hotkeys in $$$s_1, s_2, \ldots, s_n$$$ that achieve the minimum sum.

If there are several valid sets of positions, print any. You may print the words in any case.

Example
Input
3
4
invokesolutions
checktestsvalidity
printpreview
close
2
a4a
aa4
2
aa
aa
Output
YES
1 2 1 1
YES
2 1
NO