A14917 | 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$ ).

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

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