Hi everyone!

I recently came across this problem and I’m not sure how to approach it efficiently. Any hints or ideas would be appreciated!

Problem Statement

Cyclic Divisibility

Given three positive integers $$$a, b, c$$$, we need to find the smallest positive integer $$$x$$$ such that:

---

Input

The first line contains an integer $$$T$$$ — the number of test cases ($$$1 \le T \le 10^5$$$).

Each of the next $$$T$$$ lines contains three integers $$$a, b, c$$$ ($$$1 \le a, b, c \le 10^6$$$).

Output

For each test case, print a single integer — the minimum value of $$$x$$$ satisfying the conditions.

Example

Input

2
4 6 10
12 34 56

Output

30
1428

Thanks for reading!
Any ideas or hints would be appreciated :)