Floor Division GCD

You are given T test cases. For each test case, three integers l, r, and x are provided. Consider the sequence

[ \left\lfloor \frac{l}{x} \right\rfloor,; \left\lfloor \frac{l+1}{x} \right\rfloor,; \cdots,; \left\lfloor \frac{r}{x} \right\rfloor ]

Your task is to compute

[ \gcd\left(\left\lfloor \frac{l}{x} \right\rfloor,; \left\lfloor \frac{l+1}{x} \right\rfloor,; \cdots,; \left\lfloor \frac{r}{x} \right\rfloor\right) ]

Here, \(\gcd(a, b)\) denotes the greatest common divisor of a and b (e.g. \(\gcd(6,9)=3\)), and by convention the \(\gcd\) of a single positive integer is defined as the integer itself. The floor function, \(\lfloor x \rfloor\), returns the greatest integer less than or equal to \(x\) (for example, \(\lfloor 3.14 \rfloor=3\)).

Note: If the floor values are not all equal, there will exist two consecutive integers in the set, and the gcd of two consecutive integers is always 1. Thus, the answer will be \(\lfloor l/x \rfloor\) if \(\lfloor l/x \rfloor = \lfloor r/x \rfloor\); otherwise, the answer is 1.

inputFormat

The first line contains an integer T (\(1 \le T\)). Each of the following T lines contains three space-separated integers: l, r, and x.

outputFormat

For each test case, output a single line with one integer — the computed gcd value.

sample

1
20 29 10

2