Input

Input begins with a single integer t (t = 1000). t test cases follow.

Each test case starts with a line containing integer n denoting the number of words (1 <= n <= 100). Each of the next n lines contains a word - a string of between 4 and 16 characters 'a', 'b', 'c' or 'd'.

Output

For the i-th test case output a line with the text case i Y or case i N, specifying whether you wish to solve the given case. Then in the former case print a single line containing the shortest superstring. Exactly n lines with a single integer on each should follow, the i-th representing the position of the first letter of the i-th word.

Scoring

The score awarded to your program is the sum of scores taken over all test cases you chose to solve.

For each test case, the score is the fraction of the total number of characters of the words and the number of characters of the text. Programs which receive a negative score for some test case will be considered incorrect.

Example

Input:
1
4
aaaa
aaaa
aaaa
bbaaa

Output:
case 1 Y
aaaabbaaaa
1
1
7
5

Score:
17/10 = 1.7