GCDSQF  Another GCD problem
A number is squarefree if its prime descomposition contains no repeated factors. For example: 1001 = 7 * 11 * 13 is squarefree, but 20 = 2 * 2 * 5 is not squarefree.
Squarefree 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 squarefree integers A and B in binary representation compute gcd (A + B, lcm (A, B)). If the result is a squarefree 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:
20160809 05:03:52
unnecessary zeros cost me 1 WA 

surayans tiwari(http://bit.ly/1EPzcpv):
20160607 12:46:01
5600 bytes c++, AC 

SRC:
20150617 18:08:09
This is strange, no need to worry about the decimal output ! 

NISHANT RAJ:
20140314 16:50:18
who knows printing relative instead of relatively will cost 3 WA. BTW nice problem . 

Hasil Sharma:
20140109 12:35:34
good one :) 

Akshat Jain:
20131227 18:04:02
NO need of chekin for decimal output ....AC Last edit: 20131228 11:08:38 

saket diwakar:
20130128 17:52:51
loved doing this one...:) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121224 10:17:00
enjoyed solving this problem... 284B in C ;) 

V Sriharsha:
20120716 14:25:03
so easy and still 0.5 points 

~!(*(@*!@^&:
20100410 00:31:13
Text is too small. 
Added by:  Frank Rafael Arteaga 
Date:  20100207 
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 