У вас есть призовое колесо, разделенное на $$$l$$$ секций, пронумерованных от $$$0$$$ до $$$l-1$$$. Секции расположены по кругу, поэтому после секции $$$l-1$$$ нумерация продолжается снова с секции $$$0$$$.
Изначально указатель приза находится на секции $$$a$$$. Каждый раз, когда вы вращаете колесо, указатель перемещается ровно на $$$b$$$ секций вперед. То есть, после одного вращения указатель перемещается с секции $$$a$$$ на секцию $$$(a+b)\bmod l$$$, после двух вращений на $$$(a+2b)\bmod l$$$ и так далее$$$^{\text{∗}}$$$.
Вы можете вращать колесо любое количество раз (включая ноль). После того как вы остановитесь, секция, на которой в конечном итоге окажется указатель, определяет ваш приз: вы получаете сумму, равную номеру этой секции.
Какой максимальный приз вы можете получить?
$$$^{\text{∗}}$$$Здесь $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора содержит три целых числа $$$l, a$$$ и $$$b$$$ ($$$1 \le l, b \le 5000$$$, $$$0 \le a \le l-1$$$).
Для каждого набора выведите максимальный приз, который можно получить.
45 3 22 0 68 2 4100 0 1
40699
В первом наборе входных данных, прокручивая колесо три раза, а затем забирая награду, вы можете получить максимальное значение $$$4$$$. Последовательность положений указателя: $$$3, 0, 2, 4, 1, 3, 0, \ldots$$$
Во втором наборе входных данных указатель останется на секции $$$0$$$ бесконечно.
В третьем наборе входных данных, при $$$b = 1$$$ и начиная с секции $$$0$$$, указатель будет проходить через все секции, включая последнюю.
