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.

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.

提交代码