High School Programming League Problems Archive

Today, Gerrob's RSA company has featured a New RSA cryptosystem: its public key is n, the secret keys are three distinct primes p, q and r, where n=p*q*r. Note that the ordinary RSA uses only 2 primes! Unfortunately some hackers have stolen a DVD from the company. It does not store the secret keys, only some information about the system, namely, the values of:
φ (n) - Euler's totient function and
σ (n) - the sum of the divisors.
Obviously you know also n, because that's public.

Now, Gerrob's RSA employees are trying to determine if hackers will be able to break the system. Could you help them to answer this question?

Input

The first line contains a single integer T, the number of test cases, where T≤ 20000. The following T lines each contains three numbers n, φ (n) and σ (n) in this order. There are 5 input sets.

Output

Output T lines, the values of p, q and r in increasing order. It is guaranteed that p, q, r<10⁶.

Example

Input:
4
30 8 72
61321 54912 68040
451464315257 451286179344 451642497600
91896729624994213 91896040105364880 91897419147616160

Output:
2 3 5
13 53 89
6397 8039 8779
231859 574261 690187

Warning: large input/output data, be careful with certain languages.

Warning: A naive algorithm will probably solve only the first input set.