不久前,Vlad 提出了一个有趣的函数:
- $$$f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x \bmod a$$$,其中 $$$\left\lfloor\frac{x}{a}\right\rfloor$$$ 是 $$$\frac{x}{a}$$$,向下舍入,$$$x \bmod a$$$ — 整数除法的余数$$$x$$$ by $$$a$$$。
例如,对于 $$$a=3$$$ 和 $$$x=11$$$,值 $$$f_3(11) = \left\lfloor\frac{11}{3}\right\rfloor + 11 \bmod 3 = 3 + 2 = 5$$$。
数字 $$$a$$$ 是固定的并且 Vlad 知道。如果 $$$x$$$ 可以取从 $$$l$$$ 到 $$$r$$$ 之间的任何整数值($$$l \le x \le r$$$),帮助 Vlad 找到 $$$f_a(x)$$$ 的最大值。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入测试用例的数量。
接下来是 $$$t$$$ 行,每行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$a_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$$$) — 段的左右边界和固定值$$$a$$$。
输出
对于每个测试用例,在单独的行上输出一个数字 — 给定 $$$a$$$ 的给定段上函数的最大值。
示例
输入 #1
5 1 4 3 5 8 4 6 10 6 1 1000000000 1000000000 10 12 8
输出 #1
2 4 5 999999999 5
注意
在第一个示例中:
- $$$f_3(1) = \left\lfloor\frac{1}{3}\right\rfloor + 1 \bmod 3 = 0 + 1 = 1$$$,
- $$$f_3(2) = \left\lfloor\frac{2}{3}\right\rfloor + 2 \bmod 3 = 0 + 2 = 2$$$,
- $$$f_3(3) = \left\lfloor\frac{3}{3}\right\rfloor + 3 \bmod 3 = 1 + 0 = 1$$$,
- $$$f_3(4) = \left\lfloor\frac{4}{3}\right\rfloor + 4 \bmod 3 = 1 + 1 = 2$$$
作为答案,显然 $$$f_3(2)$$$ 和 $$$f_3(4)$$$ 是合适的。