P8443 gcd.

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

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$.

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.

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

**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