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 be encoded 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 must only have necessary zeros.