← 返回题目列表

Codeforces · 1650/B

B. 除法加取模

中文机器翻译题面 查看原题

不久前,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)$$$ 是合适的。