 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Elimination round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Little Vlad has two favorite numbers a and b. Recently, he was taught in school the division and multiplication operations and he immediately started dividing and multiplying his favorite numbers.
He wrote a and b in his notebook and came up with three cool operations which he wants to perform on his numbers:
 Divide both numbers by one of their common divisors;
 Divide a by one of his divisor g, multiply b by g;
 Divide b by one of his divisor g, multiply a by g.
After performing every operation he erases his old numbers, replacing them with new ones. He may choose to continue performing operations or to stop.
Since Vlad is small, he wants numbers to be smaller. Thus, he is trying to minimize sum of a and b, but can't handle it on his own. Help him to determine minimum sum that he can obtain by performing these operations and give an example of final a and b with such sum.
Input format 
Input data contains multiple test cases. The first line of input contains integer t — the number of test cases (1 ≤ t ≤ 500). Each test case is described by a single line containing integers a and b (1 ≤ a, b ≤ 10^{9}) — Vlad's favorite numbers. 

Output format 
For each test case output one line — the pair with the minimum sum that can be obtained by performing operations from the list. 
Examples 
Input data
2 4 5 4 6
Output data
1 5 2 3 
