A number is square-free if its prime decomposition contains no repeated factors. For example: 1001 = 7 * 11 * 13 is square-free, but 20 = 2 * 2 * 5 is not square-free.

Square-free numbers can encoding as binary numbers. Here are examples to illustrate:

Sequence of prime numbers 2 3 5 7 11 13 17 ...

• 42 = 2 * 3 * 7 <=> 1101
• 1001 = 7 * 11 * 13 <=> 000111
• 10 = 2 * 5 <=> 101

Your task is given two square-free integers A and B in binary representation compute gcd (A + B, lcm (A, B)). If the result is a square-free number your answer should have the binary format, if the answer is 1 print "relatively prime", and if is neither of these two cases print the result in base 10.

Input

In the first line an integer T (1 <= T <= 100) the number of test cases. The following 2 * T lines will appear integers A and B. The length of the integers A and B encoded in binary form must not exceed 1000 characters.

Output

For each of the T pairs A, B print in the specified format gcd (A + B, lcm (A, B)).

Example

Input:
2
000111
101
11
011

Output:
relatively prime
01

Note: In the input may have unnecessary zeros on the right of the numbers A and B, but Your answer only must be with necessary zeros.