1460 - 最大公约数

T 组数据,每一组数据给定 l,r,x,试求:\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor) 的值。

  • 其中 \gcd 表示求最大公约数,例如 \gcd(6,9)=3\gcd(2,4,8)=2\gcd(5,6,7)=1。特别地,我们定义一个正整数的最大公约数是它自身。
  • \lfloor x \rfloor 表示 x 向下取整,例如 \lfloor 3.14 \rfloor=3

提示

【样例解释和说明】

样例中的 T=4,说明有 4 组数据。

  • 对于第一组数据,l=3,r=6,x=1,即求 \gcd(\lfloor \frac{3}{1}\rfloor,\lfloor \frac{4}{1} \rfloor, \lfloor \frac{5}{1}\rfloor,\lfloor \frac{6}{1}\rfloor)=1
  • 对于第二组数据,l=8,r=11,x=4,即求 \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
  • 对于第三组数据,l=4,r=4,x=3,即求 \gcd(\lfloor \frac{4}{3}\rfloor)=1
  • 对于第四组数据,类似可得结果是 1

输入

第一行输入一个正整数 T,表示数据组数。

对于每一组数据,输入一行三个正整数 l,r,x,以空格隔开。

输出

对于每一组数据,输出一行,一个正整数表示答案。

样例

输入

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

输出

1
2
1
1

提示

  • 对于 10\% 的数据,x=1
  • 另有 10\% 的数据,l=r
  • 另有 20\% 的数据,r-l \leq 10^5
  • 对于上述的前 40\% 的数据,1 \leq x \leq l \leq r \leq 10^9
  • 对于所有数据,1 \leq x \leq l \leq r \leq 10^{18}1 \leq T \leq 10
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题