题目描述

不久前，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$ 被 $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$（包含两端）之间的任意整数时，$f_a(x)$ 的最大值（$l \le x \le r$）。

输入格式

输入的第一行包含一个整数 $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$ 下函数的最大值。

说明/提示

在第一个样例中：

• $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)$ 都是最大值。

由 ChatGPT 4.1 翻译

样例

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8

2
4
5
999999999
5