Description

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

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

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

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

共有 $T$ 组数据。

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

Input Format

第一行一个整数 $T$。

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

Output Format

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

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

1
7
45
44
21860