MNIU - My Name is UMMM!

In a country far away there is a kind of a competition called programming contests. As they are becoming increasingly popular, they get regular coverage on newspapers. That's the only positive part of the story. The quality of their reports are not up to the mark and often hilarious for the competitive programming community. The reporters often mix up names - exchanging words from one person's name to someone else's name.

Chowdhury Shaheb - a curious programmer analyzed the reports and found a very interesting pattern. He saw whenever any word of two person's names have the same first and last letters and at least one additional common letter, journalists will mix them up. For example: The words 'Manjur' and 'Mazumder' have same first and last letters and two common letters 'a' and 'u'.

You'll be given a pair of names. List all possible confusing name variations of those two names. A confusing variation of a name is obtained by changing at least one word of that name to a similar word (according to the aforementioned pattern) from the other's name. A variation is not considered confusing if it is exactly same to any of the given names. See the input and output format section for more details.

Input

First line of input will contain a single integer T (1 <= T <= 15), the number of testcases. It will be followed by T sets of testcases. Each set of testcase will contain two lines, each line will contain a name. Each name will contain no more than 20 characters. Names will have no more than 3 words, each word will consist of only English letters ('A'- 'Z', 'a'-'z'). First letter of a word will always be capitalized and others are in lowercase. Each word of a name will be separated by exactly one space between them.

Output

First line of the output of each test case should contain the case number (In this format: Case <caseNumber>:). From the next line, print all the confusing variations - one per line in ascending lexicographic order. A name X is lexicographically smaller than another name B if it contains a smaller letter at the first position they differ or if X is a prefix of Y. A space is smaller than any other English character. If there is no confusing name, print "None" (without the quotes). Print a blank line between testcases.

Sample

Input
3
Syed Shahriar Manjur
Pratyai Mazumder
Tasnim Imran Sunny
Sabbir Yousuf Sanny
Md Hafiz Uddin
Sohel Hafiz

Output
Case 1:
Pratyai Manjur
Syed Shahriar Mazumder

Case 2:
Sabbir Yousuf Sunny
Tasnim Imran Sanny

Case 3:
None

Problem Setter: Mir Wasi Ahmed

Special Thanks: Ahmad Faiyaz


Added by:Faiyaz
Date:2013-12-30
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-02-07 22:13:42 nani
can please anyone tell me if input is:
1
X11x X12x X13x
X14x X15x X16x
then can "X12x X13x X11x" be one of output?

Last edit: 2014-04-24 05:50:12
2014-01-31 13:18:08 Hector Monteo
Can someone give me a test case?
2014-01-09 15:36:50 [Lakshman]
@Ahmad Faiyaz Can you Please reply?
2014-01-02 08:29:05 Jacob Plachta
Hmm, is the data definitely correct? I'm pretty sure I've read the problem correctly.

Reply:
Yes, Judge data is correct. We have used this problem on a online programming contest, where many people got AC. Maybe you are missing something. I have seen your output, you are really missing something. :)

RE: Oops, there was indeed a silly bug. Thanks!

Last edit: 2014-01-02 15:23:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.