In preparation for the ACM/ICPC in Hanoi in 2020, a huge amount of robots is needed to serve as volunteers. However, the organizers own only a certain number of robots. Fortunately, these robots can automatically duplicate themselves. More precisely, a group of R robots together in T time units can build a new robot like themselves. The new robot also has the ability to join a group of robots to build another robot. Each robot can join only one group for building new robots at a time.
For example with R=4 and T=6, a group of 4 initial robots takes 6 time units to build the 5th robot,
another 6 time units to build the 6th robot, another 6 time unit to build the 7th robot, and another 6 time unit
to build the 8th robot. After that, two groups can be formed to build new robot concurrently, which take
only 6 time unit to build 2 new robots. So it takes 30 time units to have 10 robots from 4 initial robots.
Given 3 positive integers R, T and N (1 ≤ R ≤ 1024, 1 ≤ T ≤ 104, R < N ≤ 109), your task is to write a program to determine the smallest time units required to build a team of N robots from R initial robots.
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 30. The following lines describe the data sets.
Each data set consists of only one line that contains three integers R, T and N separated by a space.
each data set, write in a single line the smallest time unit required.
2 4 6 10 4 6 11
30 36
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|