Can you find it?

Time Limit: 1000MS

Memory Limit: 65535K

Description

Hi smart guys, you must know thecommon divisor of two integers. But do you know the common divisor of twostrings.

Now,let’s define the it. First, you should know the divisor of a string : Given a stringstr, if there is a string sub, and we can get string str by write string sub ttimes, where t is an integer. For example string “abab” has two divisors “ab”and “abab”. Now you must have guessed the common divisor of the twostrings.  Your task is that given twostrings, find the smallest common divisor of them.

Input

First line of input is an integerT(1<=T<=300) indicate the number of test case.

The next 2T lines, each line have a non-empty string, every two lines indicating a test case.

The length of every string not exceed 10000, and only consist of lowercase letters.

Output

For each case output the smallest common divisor of the two string in one line. If they have no common divisor, just output “I am just kidding!” in one line.

Sample Input

3
aa
aaa
abcabc
abcabcabcabc
aaa
bbb

Sample Output

a
abc
I am just kidding!

Hint

None

Source

杨超

提交代码