Монокарп руководит компанией. Рассмотрим работу его компании в течение ближайших $$$k$$$ месяцев. В первом месяце в компании работают $$$x$$$ сотрудников, не считая самого Монокарпа, и нужно выполнить $$$y$$$ проектов. В каждом следующем месяце и число сотрудников, и число проектов увеличивается на $$$1$$$.
Иными словами, в месяце с номером $$$i$$$ ($$$0 \le i \lt k$$$) в компании работают $$$x+i$$$ сотрудников и нужно выполнить $$$y+i$$$ проектов.
В каждом месяце Монокарп распределяет проекты между сотрудниками. Каждый сотрудник должен получить одинаковое число проектов, а каждый проект можно назначить не более чем одному сотруднику. Все неназначенные проекты Монокарп выполняет сам. Он всегда выбирает распределение, при котором ему приходится выполнить как можно меньше проектов.
В частности, если в некотором месяце имеется $$$a$$$ сотрудников и $$$b$$$ проектов, то Монокарп назначает каждому сотруднику ровно $$$\left\lfloor \frac{b}{a} \right\rfloor$$$ проектов, а сам выполняет $$$b \bmod a$$$ проектов.
Найдите суммарное количество проектов, которые Монокарп выполнит сам за ближайшие $$$k$$$ месяцев.
В первой строке дано целое число $$$t$$$ — число наборов входных данных ($$$1 \le t \le 10^4$$$).
Каждый набор входных данных состоит из одной строки, содержащей три целых числа $$$x$$$, $$$y$$$ и $$$k$$$ ($$$1 \le x \le y \le 10^6$$$; $$$1 \le k \le 10^{12}$$$).
Дополнительное ограничение на входные данные:
Для каждого набора входных данных выведите одно целое число — суммарное количество проектов, которые Монокарп выполнит сам за $$$k$$$ месяцев.
71 1 13 10 23 8 67 20 110 25 1008 36 171 999900 1000000000000
041861425110999898177699820694
В первом наборе единственный сотрудник выполняет единственный проект, поэтому Монокарпу не остаётся ни одного проекта.
Во втором наборе в первом месяце $$$10$$$ проектов распределяются между $$$3$$$ сотрудниками: каждый получает по $$$3$$$ проекта, а Монокарп выполняет $$$1$$$ проект. Во втором месяце $$$11$$$ проектов распределяются между $$$4$$$ сотрудниками: каждый получает по $$$2$$$ проекта, а Монокарп выполняет $$$3$$$ проекта. Ответ равен $$$1 + 3 = 4$$$.
В третьем наборе число проектов, выполняемых Монокарпом в шести месяцах, равно $$$2$$$, $$$1$$$, $$$0$$$, $$$5$$$, $$$5$$$ и $$$5$$$ соответственно. Их сумма равна $$$2 + 1 + 0 + 5 + 5 + 5 = 18$$$.
