题目描述

Ranran needs to prepare a contest! A contest is made of $c$ problems, and Ranran can do one of the following two things:

• Clone himself in $a$ minutes. That is, after $a$ minutes, there will be one more Ranran.
• Prepare a problem in $b$ minutes. That is, after $b$ minutes, there will be one more problem.

Note that a cloned Ranran can also do the two things above. A Ranran cannot do the two things at the same time.

Ranran wants to prepare the contest as fast as possible. But he is very lazy, so he asks you to find the minimum number of minutes to prepare the contest.

You need to answer $T$ queries independently.

输入格式

The first line contains an integer $T$ ($1\leq T\leq 10 ^ 5$).

Each of the next $T$ lines contains three integers $a$, $b$ and $c$ ($1\leq a, b, c\leq 10 ^ 9$), representing a query.

输出格式

For each test case, output a line with a single integer representing the answer.

题目大意

题目描述

然然需要准备一场有 $c$ 个问题的比赛！他可以进行两种操作：

• 在 $a$ 分钟内克隆一个自己；
• 在 $b$ 分钟内准备好一个问题。

克隆的然然也可以进行上述操作，但然然不能同时进行这两个操作。

然然希望尽快准备好比赛，但是他很懒，所以他让你求出准备比赛的最小分钟数。

共有 $T$ 组数据。

$1\leq T\leq 10 ^ 5$，$1\leq a, b, c\leq 10 ^ 9$。

输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行三个整数 $a, b, c$。

输出格式

对于每组数据，输出一行一个整数表示答案。

5
1 1 1
2 3 3
9 9 9
3 26 47
1064 822 1048576

1
7
45
44
21860

提示

Source: The 2022 ICPC Asia Xi'an Regional Contest Problem C.

Author: MagicSpark.