Background

I borrow a spark from you, and use it to write about mountains and rivers.

Problem Description

There are $T$ test cases. For each test case, you are given $l, r, x$. Find the value of $\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor)$.

• Here $\gcd$ means the greatest common divisor. For example, $\gcd(6,9)=3$, $\gcd(2,4,8)=2$, $\gcd(5,6,7)=1$. In particular, we define that the greatest common divisor of a positive integer is itself.
• $\lfloor x \rfloor$ means rounding $x$ down. For example, $\lfloor 3.14 \rfloor=3$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case, one line contains three positive integers $l, r, x$, separated by spaces.

Output Format

For each test case, output one line with a positive integer representing the answer.

4
3 6 1
8 11 4
4 4 3
7 16 2

1
2
1
1

Hint

Sample Explanation and Notes

In the sample, $T=4$, which means there are $4$ test cases.

• For the first test case, $l=3,r=6,x=1$, so we compute $\gcd(\lfloor \frac{3}{1}\rfloor,\lfloor \frac{4}{1} \rfloor, \lfloor \frac{5}{1}\rfloor,\lfloor \frac{6}{1}\rfloor)=1$.
• For the second test case, $l=8,r=11,x=4$, so we compute $\gcd(\lfloor \frac{8}{4} \rfloor,\lfloor \frac{9}{4} \rfloor,\lfloor \frac{10}{4}\rfloor,\lfloor \frac{11}{4}\rfloor)=\gcd(2,2,2,2)=2$.
• For the third test case, $l=4,r=4,x=3$, so we compute $\gcd(\lfloor \frac{4}{3}\rfloor)=1$.
• For the fourth test case, similarly, the result is $1$.

Constraints

• For $10\%$ of the data, $x=1$.
• For another $10\%$ of the data, $l=r$.
• For another $20\%$ of the data, $r-l \leq 10^5$.
• For the first $40\%$ of the data above, $1 \leq x \leq l \leq r \leq 10^9$.
• For all data, $1 \leq x \leq l \leq r \leq 10^{18}$, $1 \leq T \leq 10$.

Translated by ChatGPT 5