题目描述

你有两个互相啮合的齿轮，要求齿轮 A 每转 $a$ 圈时，齿轮 B 恰好转 $b$ 圈。

由于工艺精度要求，每个齿轮的齿数不得少于 $c$。在满足上述条件的前提下，求齿轮 A 与齿轮 B 的齿数之和的最小值。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$，表示数据组数。接下来每组数据占一行，包含三个整数 $a, b, c$。

输出格式

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

样例

3
2 3 4
4 8 5
5 2 8

10
15
28

提示

样例解释

• 第一组：齿轮 A 有 $6$ 齿，齿轮 B 有 $4$ 齿，答案 $6 + 4 = 10$；
• 第二组：齿轮 A 有 $10$ 齿，齿轮 B 有 $5$ 齿，答案 $10 + 5 = 15$；
• 第三组：齿轮 A 有 $8$ 齿，齿轮 B 有 $20$ 齿，答案 $8 + 20 = 28$。

数据规模

令 $v = \max(a, b, c)$。

• Subtask 0（13 pts）：$v \le 20$；
• Subtask 1（13 pts）：$v \le 5000$；
• Subtask 2（20 pts）：$v \le 10^6$；
• Subtask 3（54 pts）：无特殊限制。

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