GCDSQF - Another GCD problem

no tags 

A number is 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.

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.


hide comments
darryl: 2016-08-09 05:03:52

unnecessary zeros cost me 1 WA

surayans tiwari(http://bit.ly/1EPzcpv): 2016-06-07 12:46:01

5600 bytes c++, AC

SRC: 2015-06-17 18:08:09

This is strange, no need to worry about the decimal output !

NISHANT RAJ: 2014-03-14 16:50:18

who knows printing relative instead of relatively will cost 3 WA. BTW nice problem .

Hasil Sharma: 2014-01-09 12:35:34

good one :)

Akshat Jain: 2013-12-27 18:04:02

NO need of chekin for decimal output ....AC

Last edit: 2013-12-28 11:08:38
saket diwakar: 2013-01-28 17:52:51

loved doing this one...:)

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-24 10:17:00

enjoyed solving this problem... 284B in C ;-)

V Sriharsha: 2012-07-16 14:25:03

so easy and still 0.5 points

~!(*(@*!@^&: 2010-04-10 00:31:13

Text is too small.


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