HS08CODE - Break a New RSA system

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<106.

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.


Added by:Robert Gerbicz
Date:2009-04-08
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League 2008/09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.