Ranran 需要准备一场比赛！一场比赛由 $c$ 道题目组成，Ranran 可以做以下两件事之一：

• 花费 $a$ 分钟克隆自己。也就是说，经过 $a$ 分钟后，会多出一个 Ranran。
• 花费 $b$ 分钟准备一道题目。也就是说，经过 $b$ 分钟后，会多出一道题目。

注意，克隆出来的 Ranran 也可以执行上述两件事。一个 Ranran 不能同时做这两件事。

Ranran 想尽快准备好这场比赛。但他非常懒，所以他请你求出准备这场比赛所需的最少分钟数。

你需要独立回答 $T$ 组询问。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)。

接下来 $T$ 行，每行包含三个整数 $a, b$ 和 $c$ ($1 \le a, b, c \le 10^9$)，代表一组询问。

输出格式

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

样例

输入 1

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

输出 1

1
7
45
44
21860