Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

GCD and NOD

By forthright48 · Limits 500ms, 512 MB

Given 3 numbers, G, A and B we have to find two numbers M and N such that they satisfy the following conditions:

  • M and N have no other prime divisor except 2 and 3
  • Greatest common divisor of M and N is G
  • Number of divisor of M is A
  • Number of divisor of N is B
  • M is between 1 and 1018
  • N is between 1 and 1018

It is possible that multiple pairs of M and N satisfy the above conditions. In such a case, we want to find the pair where M is minimum. If there is still tie, then we minimize N.

It is guaranteed that a solution always exists.

Input

The first line contains a single integer T (T ≤ 100) denoting number of test case. The next T lines describes each test case. Each test case is a single line containing three integers: G, A and B.

Output

For each test case, output a single line containing two integers: M and N satisfying the conditions mentioned in problem statement above.

Sample

Input Output
2
1 2 2
6 6 8
2 3
12 54

Discussion

Statistics


38% Solution Ratio

DayamoyEarliest, Aug '17

rubbyEFastest, 0.0s

DayamoyLightest, 131 kB

AnachorShortest, 791B

Submit

Login to submit

Related Contests

ProgKriya May'16 Ended at 2016-05-01 16:00:00 +0000 UTC
Ardent Programmers' Team Practice Contest for ICPC 2019 Ended at 2019-11-01 09:00:00 +0000 UTC