Elimination round completed

Tasks

Show one task per page / all tasks on one page

"A" Small Numbers
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 ≤ 109) — 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
 

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?

Registration

The instruction for password recovery
has been sent to your email