Contest Preparation

Ranran is preparing a contest consisting of \( c \) problems. Initially, there is one Ranran. Each Ranran can perform one of the following two actions:

• Clone himself in \( a \) minutes (after \( a \) minutes, there will be one more Ranran).
• Prepare a problem in \( b \) minutes (after \( b \) minutes, there will be one more problem).

Note that a cloned Ranran can also perform these actions, and no Ranran can perform both actions simultaneously. All actions performed by different Ranrans run concurrently.

Ranran wants to prepare the contest as fast as possible. He asks you to determine the minimum number of minutes needed to prepare \( c \) problems optimally. You have to answer \( T \) queries independently.

Optimal Strategy Hint: It is optimal to perform some number of cloning rounds to increase the number of Ranrans, and then use the available Ranrans to prepare the problems concurrently. If you do \( p \) cloning rounds, the number of Ranrans becomes \( 2^p \) and you then require \( \lceil c/2^p \rceil \) rounds of problem preparation.

inputFormat

The first line contains an integer \( T \) (\(1 \le T \le 10^4\)), the number of test cases.

Each of the next \( T \) lines contains three space-separated integers \( a \), \( b \), and \( c \) (\(1 \le a, b \le 10^9\) and \(1 \le c \le 10^9\)), representing the time to clone, the time to prepare one problem, and the total number of problems needed, respectively.

outputFormat

For each test case, output one integer — the minimum number of minutes required to prepare the contest.

sample

1
1 100 100

107