题目描述

你有两个啮合在一起的齿轮，你希望齿轮 A 每转 $a$ 圈齿轮 B 都能转恰好 $b$ 圈。

由于精细度要求，每个齿轮都必须有不少于 $c$ 个齿，求齿轮 A 和齿轮 B 的总齿数和的最小值。

输入格式

本题有多组数据。

第一行一个整数 $T$ 描述数据组数。对于每组数据：

• 仅一行，三个整数 $a, b, c$。

输出格式

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

样例 #1

样例输入 #1

3
2 3 4
4 8 5
5 2 8

样例输出 #1

10
15
28

提示

样例解释

• 对于第一组数据，最优方案为齿轮 A 有 $6$ 个齿，齿轮 B 有 $4$ 个齿，答案为 $4 + 6 = 10$；
• 对于第二组数据，最优方案为齿轮 A 有 $10$ 个齿，齿轮 B 有 $5$ 个齿，答案为 $10 + 5 = 15$；
• 对于第三组数据，最优方案为齿轮 A 有 $8$ 个齿，齿轮 B 有 $20$ 个齿，答案为 $8 + 20 = 28$。

数据规模与约定

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

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

对于所有数据，保证 $1 \leq T \leq 8\times 10^3$，$1 \leq a, b, c \leq 10^9$。