Не так давно Влад придумал интересную функцию:
Например при \(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\).
В первом примере:
В качестве ответа, очевидно, подходят \(f_3(2)\) и \(f_3(4)\).
5 1 4 3 5 8 4 6 10 6 1 1000000000 1000000000 10 12 8
2 4 5 999999999 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач