SP6059 GCDSQF - Another GCD problem

A number is [square-free](http://en.wikipedia.org/wiki/Square-free_integer "Square-free") if its prime descomposition 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.

In the first line an integer T (1

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