HS08CODE - Break a New RSA system

no tags 

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.


hide comments
David: 2021-08-06 16:44:08

No Java solutions. Time limit too strict for O(1) Java solution. Able to solve 20K cases in 0.054 sec on desktop.

Last edit: 2021-08-06 16:45:33
Francky: 2017-02-10 17:58:39

Now it's possible using Python3. At last ;-)

Francky: 2016-06-24 19:42:26

With several input files, if your solution is near 0.01 per big file, you can get here 0.03s or even 0.00s with the same source code ! Here I think there's 3 big files, one medium and a small one. I'll try a PY3.4 solution.
@rainy jain : we can't do better than O(1), but there's several options...

(Edit) : TLE using PY3.4 for me. On my hardware (Intel i5-2400) with 2.000.000 input lines, 1.5s with the C-code, and 13s with the PY3.4 one. So we can say that TL is strict here for slow languages. I think I'm not so far...

Last edit: 2016-06-24 21:31:31
rainy jain : 2016-06-11 11:35:59

What is the expected complexity.My O(1) code is also getting TLE.

爆炸王旭: 2012-12-04 12:42:10

I wonder how those ACers pass time limit... I have submitted 2 programs in PASCAL and C++, but both of them are
TLE...

shubhang singh chauhan: 2012-07-22 17:06:57

really its very tough to pass time limit.

mukesh tiwari: 2011-08-01 15:47:21

time limit is too strict for functional languages.

abhijith reddy d: 2009-06-14 01:37:55

+1 same here...20000 testcases :D

Tony Beta Lambda: 2009-06-13 15:28:15

0.400s time limit - isn't it too strict?


Added by:Robert Gerbicz
Date:2009-04-08
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:High School Programming League 2008/09