#P3018. 这个很难,先别写这个

这个很难,先别写这个

题目描述

不久前,lcylcy提出了一个有趣的函数:

  • $f_a(x) = \left \lfloor \frac{x}{a} \right \rfloor + (x \bmod a)$,其中 \lfloor \rfloor 表示向下取整,xmodax \bmod a 表示除以 aa 的余数。

例如,对于 a=3a = 3x=11x = 11,值为:

$$f_3(11) = \left \lfloor \frac{11}{3} \right \rfloor + (11 \bmod 3) = 3 + 2 = 5 $$

给定固定的 aa,请帮助lcylcy找到 fa(x)f_a(x) 的最大值,如果 xx 可以取区间 [l,r][l, r] 中的任意整数值。

输入格式

第一行一个整数 tt1t1041 \leq t \leq 10^4)—— 测试用例数量。

接下来 tt 行,每行三个整数 li,ri,ail_i, r_i, a_i1liri1091 \leq l_i \leq r_i \leq 10^91ai1091 \leq a_i \leq 10^9)—— 区间左右边界和固定的 aa

输出格式

对于每个测试用例,输出一个整数,表示给定区间上函数的最大值。

样例

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
2
4
5
999999999
5
  • 第一个样例中:

    • f3(1)=0+1=1f_3(1) = 0 + 1 = 1
    • f3(2)=0+2=2f_3(2) = 0 + 2 = 2
    • f3(3)=1+0=1f_3(3) = 1 + 0 = 1
    • f3(4)=1+1=2f_3(4) = 1 + 1 = 2

    最大值是 22