题目背景

M 城遭遇垃圾围城，环卫局紧急启用了可以自我复制的新一代清洁机器人。

题目描述

初始时只有 $1$ 台清洁机器人，它具备两种工作模式：

• 复制：花费 $a$ 秒克隆出一台与自身完全相同的新机器人，新机器人同样具备复制与清理的能力；
• 清理：一台机器人处理一袋垃圾需要 $b$ 秒。

所有机器人可以同时各自工作；但同一台机器人同一时刻只能进行复制与清理中的一种。 现在共有 $c$ 袋垃圾需要处理。请求出完成全部清理所需的最短时间（单位：秒）。

输入格式

第一行一个整数 $T$，表示测试用例数。接下来 $T$ 行，每行三个整数 $a, b, c$。

输出格式

共 $T$ 行，每行一个整数，表示对应测试用例的最短时间。

样例

样例 1 输入

3
3 4 5
1 10 10
100 1 1

样例 1 输出

13
14
1

样例说明：第一组中，克隆 3 次得到 8 台机器人（耗时 9 秒），处理 5 袋垃圾需要 $\lceil 5/8\rceil=1$ 轮（耗时 4 秒），共 13 秒，为最优。第三组直接处理仅需 1 秒。

样例说明

第一组：克隆 $3$ 次得到 $2^3 = 8$ 台机器人，耗时 $3 \times 3 = 9$ 秒；$8$ 台机器人处理 $5$ 袋垃圾需要 $\lceil 5 / 8 \rceil = 1$ 轮，耗时 $4$ 秒；共 $13$ 秒，为最优。

第三组：直接处理只需 $1$ 秒。

数据范围与提示

对于全部数据：$1 \le T \le 10^5$，$1 \le a, b, c \le 10^9$。

时间限制：1 秒；内存限制：512 MB。