题目背景

垒球是橙色的 网球是绿色的。网球是上升的，网球是下落的。

And you never meet the people, you never shake their hands, you never hear their story or tell yours.
But somehow in the act of making something with a great deal of care and love, something's transmitted there.

题目描述

你有两个啮合在一起的齿轮，你希望齿轮 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$ 个齿，答案为 $4 + 6 = 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 \leq 20$；
• Subtask 1（13 pts）：$v \leq 5000$；
• Subtask 2（20 pts）：$v \leq 10^6$；
• Subtask 3（54 pts）：无特殊限制。

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