TIGA - Nuts Frenzy


Ivan, Filbert, and Tracy really like nuts. They can eat nuts without stopping all day long if they want to. Today they decided to buy some nuts so each one of them get exactly K nuts (1<=K<=1,000,000,000) and they want to eat it all. To make it interesting, they are only allowed to eat a certain number of nuts every second.

  • Ivan can eat at max I nuts per second. (1<=I<=1,000,000)
  • Filbert can eat at max K/F nuts per second. (1<=F<=100)
  • Tracy can eat at max the sum of all the factors of K excluding 1 and K nuts per second.

They are not allowed to eat only a fraction of a nut every second, and they must eat a minimum of 1 nut every second regardless of the previous rule. They can stop eating after they run out of nuts. Your task is to determine the time needed (in seconds) for each of them to finish their nuts!

Input

The first line of input is T, the number of test case. (T<20)
The next T lines each consists of three numbers K, I, and separated by a space.

Output

For each test case, output the minimum time needed for Ivan, Filbert, and Tracy to finish their nuts.

Example

Input:

3
10 2 5
100 10 4
121 100 1

Output:

5 5 2
10 4 1
2 1 11


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-10-23 15:02:13

Oh ya, I forgot about the start up time :-P sorry..

Francky: 2012-10-23 15:02:13

@tjandra : no, you didn't count start up time for them.

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-23 15:02:13

ok, now I realized that python 2 is 16x faster than python 3 for this problem...

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-23 15:02:13

Nice problem, I got AC with perfect time 0.00s :-D


Added by:Andy
Date:2012-10-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem