GCDSQF - Another GCD problem

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.


Added by:Frank Rafael Arteaga
Date:2010-02-07
Time limit:0.100s
Source limit:6000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem, Discrete Math

hide comments
2010-04-10 00:31:13 ~!(*(@*!@^&
Text is too small.
2010-02-13 18:27:44 Paranoid Android
Using gets to take input gives WA. Use scanf.
2010-02-09 23:08:28 Frank Rafael Arteaga
[Trichromatic] XilinX, I don't know your e-mail.

RE by XilinX: Use this link.

Last edit: 2010-02-12 02:05:25
2010-02-09 03:38:51 [Rampage] Blue.Mary
Er, you may e-mail me your data generator and set me as co-author of this problem, I can help you upload data :)
2010-02-08 19:03:05 Frank Rafael Arteaga
I understand yuor argument. I dont like very strict time too, but I do not have enough internet to upload large files. I tried my code in Python and gives in 0.25s. Clear the brute force algorithm will not at this time even in C++.
2010-02-08 04:57:26 Jorge Bernadas
Generally here, problems with Time Limits lower than 1s are not seen with good eyes. The 0.3s might be too harsh for most languages.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.