B. DIV + MOD
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Не так давно Влад придумал интересную функцию:

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

Входные данные

В первой строке входных данных записано целое число $$$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$$$.

Пример
Входные данные
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
Выходные данные
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)$$$.