F. Greatest Common Mutiple
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Despite being best girl, Kirisu-sensei still is terrible at math. She has combined the concepts of greatest common factor and least common multiple together!

The greatest common multiple of two numbers $$$a$$$ and $$$b$$$ (gcm) is the largest number that both $$$a$$$ and $$$b$$$ can divide. Since this number is very large (in fact it's infinite), you are asked to find it mod some number $$$c$$$. In this context, largest under mod means the maximum value of $$$(d \text{ mod } c)$$$ over any $$$d$$$ that both $$$a$$$ and $$$b$$$ divide $$$d$$$.

In mathematical terms,

$$$$$$x = \max_{a \mid d, b \mid d}(d \text{ mod } c)$$$$$$

output $$$x$$$ as defined above ($$$a \mid d$$$ means that $$$a$$$ divides $$$d$$$).

Input

The first line contains one integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 3366)$$$.

The following $$$T$$$ lines each contain three integers $$$a, b, c$$$, where $$$a$$$ and $$$b$$$ are the two numbers to find the gcm of and $$$c$$$ is the mod $$$(1 \leq a, b \lt c \leq 10^9)$$$.

Output

For each testcase, output $$$\text{gcm}(a, b) \mod c$$$ or $$$\max_{a \mid d, b \mid d}(d \text{ mod } c)$$$.

Example
Input
5
2 3 10
3 7 10
4 2 2023
33 66 3366
103241 103870 100000007
Output
8
9
2022
3300
100000006
Note

If we pick $$$d = 18$$$ on the first sample, we would output $$$x = 18 \text{ mod } 10$$$. It is impossible to have a better answer. Note that $$$d = 48$$$ or $$$d = 888888$$$ also give a maximal $$$x = 8$$$.

In the second sample, picking $$$d = 189$$$ gives a maximal $$$x = 9$$$.

The two auspicious $$$6$$$-digit numbers are codeforces gym IDs to remind us to upsolve some of our previous contests <3.

 —

Idea: 3366

Preparation: 3366

Occurances: Novice 6