CF1650B.DIV + MOD

Not so long ago, Vlad came up with an interesting function:

• $f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x \bmod a$, where $\left\lfloor\frac{x}{a}\right\rfloor$ is $\frac{x}{a}$, rounded down, $x \bmod a$ — the remainder of the integer division of $x$ by $a$.

For example, with $a=3$ and $x=11$, the value $f_3(11) = \left\lfloor\frac{11}{3}\right\rfloor + 11 \bmod 3 = 3 + 2 = 5$.

The number $a$ is fixed and known to Vlad. Help Vlad find the maximum value of $f_a(x)$ if $x$ can take any integer value from $l$ to $r$ inclusive ($l \le x \le r$).

不久之前，弗拉德提出了一个有趣的函数：

• $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$ 是固定的，且弗拉德已知其值。请帮助弗拉德找出 $f_a(x)$ 在 $x$ 取 $l$ 到 $r$（含端点）之间任意整数值时所能达到的最大值（即 $l \le x \le r$）。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases.

This is followed by $t$ lines, each of which contains three integers $l_i$, $r_i$ and $a_i$ ($1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$) — the left and right boundaries of the segment and the fixed value of $a$.

输入数据的第一行包含一个整数 $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$。

For each test case, output one number on a separate line — the maximum value of the function on a given segment for a given $a$.

对于每个测试用例，在单独一行输出一个数字——该函数在给定区间上、对于给定 $a$ 的最大值。

In the first sample:

• $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$

As an answer, obviously, $f_3(2)$ and $f_3(4)$ are suitable.

在第一个样例中：

• $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)$。