Programming League 2004/05

One day when Johnny was still a schoolboy he got caught red-handed by his teacher while doing a Very Mischievous Thing (of the sort that you would expect of Johnny). As a punishment he was told off and assigned additional homework. The teacher underlined quite a few words in a dictionary and asked Johnny to rewrite all of them to his notebook.

Johnny wasn't at all pleased about this, since writing by hand is always a painful burden. Fortunately, Johnny's dad took pity on the crying boy and offered to help. He presented his son with a few sheets of carbon paper, thanks to which any text Johnny wrote was at once ready in exactly k copies. Some of the characters of particular copies could then be erased using a white correction pen, so as to obtain only the words required by the teacher. All the characters forming a single word have to be directly adjacent, but words can be written in any order on the sheets and different words can be separated by an arbitrary (possibly 0) amount of space.

Johnny has cheered up considerably by now, since the bit with the carbon paper and correction pen sounds rather fun. All that remains to be done is to write down an appropriate text, obviously keeping it as short as possible. Please advise Johnny what to write.

Input

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

Each test case starts with a line containing two integers n k, respectively denoting the number of words the teacher has asked Johnny to write and the total number of carbon copies that Johnny creates, including the original (1<=k<=n<=512). Each of the next n lines contains a word assigned by the teacher - a string of between 4 and 12 characters 'a', 'b', 'c' or 'd'. All words given at input are Bytelandian nouns in common use.

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 text that should be written by Johnny. 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 (on the page on which this word eventually appears, before applying the correction pen).

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 difference between the total number of characters of the words provided by the teacher and the number of characters of the text eventually handwritten by Johnny. Programs which receive a negative score for some test case will be considered incorrect.

Example

Input:
1
4 2
aaaa
aaaa
aaaa
bbaaa

Output:
case 1 Y
aaaabbaaaa
1
1
7
5

Score:
17 - 10 = 7

When given in to the teacher, the 2 pages of homework may look as follows:

aaaa__aaaa
aaaabbaaa_