Background

Baseball is orange Tennis is green. Tennis is rising, tennis is falling.

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.

Problem Description

You have two gears meshed together. You want that every time gear A rotates $a$ turns, gear B rotates exactly $b$ turns.

Because of precision requirements, each gear must have at least $c$ teeth. Find the minimum possible value of the sum of the numbers of teeth of gear A and gear B.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$ describing the number of test cases. For each test case:

• One line with three integers $a, b, c$.

Output Format

For each test case, output one integer per line, representing the answer.

3
2 3 4
4 8 5
5 2 8

10
15
28

Hint

Sample Explanation

• For the first test case, the optimal solution is that gear A has $6$ teeth and gear B has $4$ teeth, so the answer is $4 + 6 = 10$.
• For the second test case, the optimal solution is that gear A has $10$ teeth and gear B has $5$ teeth, so the answer is $10 + 5 = 15$.
• For the third test case, the optimal solution is that gear A has $8$ teeth and gear B has $20$ teeth, so the answer is $8 + 20 = 28$.

Constraints and Notes

This problem uses bundled testdata.

Let $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): No special restrictions.

For all testdata, it is guaranteed that $1 \leq T \leq 8\times 10^3$ and $1 \leq a, b, c \leq 10^9$.

Input Format

Output Format

Translated by ChatGPT 5