B. 熙巨打票
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

众所周知，熙巨最近参加的 icpc-ec-final，回到长沙的时候，需要报销车费凭证，火车站只有两台机器。

长沙火车站报销机

但是由于机器非常卡顿，每次只能导出1张凭证，并且在每导出一张后需要冷却 a, a ≤ 100 分钟，熙巨每次操作需要 b ≤ 100 分钟，并且同一时刻只能在一个机器上进行操作。由于熙巨有 n, n ≤ 109 张车票需要打，熙巨不想浪费时间，他想知道，最少打完票需要多长时间。

Input

第一行一个整数 T，表示测试样例数量

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

数据保证 0 ≤ a ≤ 100, 1 ≤ b ≤ 100, 1 ≤ n ≤ 109, T ≤ 105

Output

输出 T 行，每行一个正整数，表示最小需要的时间。

Example
Input
4
10 4 10
5 5 15
7 8 1
1 3 12
Output
64
75
8
36