409518: GYM103608 A В погоне за Пингвином

A. В погоне за Пингвиномограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Брюс Уэйн гонится за помощником Фальконе по прозвищу Пингвин на бэтмобиле по плоскости.

Из-за взрыва бэтмобиль повреждается и теперь может перемещаться только на один вперед и на один вправо. При этом, движение прямо тратит $$$a$$$ единиц топлива, а вправо — $$$b$$$ единиц топлива.

Сейчас машина супергероя находится в точке $$$(0, 0)$$$ и имеет в баке $$$f$$$ топлива. Когда топливо закончится, бэтмобиль не сможет больше перемещаться и герою придется догонять злодея бегом.

Определите, сколько существует точек с целочисленными координатами, до которых Бэтмен все еще может добраться на своем бэтмобиле.

Как известно, все супергерои обычно существуют в $$$t$$$ параллельных вселенных. Поэтому решите эту задачу для каждой из параллельных вселенных.

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

В первой строке входных данных дано целое число $$$t$$$ — количество вселенных, в которых необходимо решить задачу ($$$1 \leqslant t \leqslant 500$$$).

Каждая из следующих $$$t$$$ строк ввода описывает одну вселенную. В $$$i$$$-й из них через пробел даны целые числа $$$a_i$$$, $$$b_i$$$ и $$$f_i$$$ — затраты топлива на перемещение на один вперед, затраты топлива на перемещение на один вправо, начальный объем топлива в баке бэтмобиля ($$$1 \leqslant a_i, b_i, f_i \leqslant 10^9$$$).

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

Выведите ответ на задачу для каждой из вселенных в отдельной строке. Каждый ответ должен состоять из единственного целого числа — количества достижимых на бэтмобиле целочисленных точек.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи	Информация о проверке
1	15	$$$t \leqslant 5$$$, $$$a_i, b_i, s_i \leqslant 10$$$	–	полная
2	15	$$$t \leqslant 100$$$, $$$a_i, b_i, s_i \leqslant 100$$$ для всех $$$i$$$	1	полная
3	14	$$$s_i$$$ делится на $$$a_i$$$ и $$$b_i$$$ для всех $$$i$$$	–	полная
4	20	$$$a_i \geqslant 10^5$$$	–	полная
5	18	$$$a_i = 1$$$ для всех $$$i$$$	–	полная
6	18	нет	1 – 5	первая ошибка

ПримерыВходные данные

3
3 2 9
1 4 17
1 1 8

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

12
50
45

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

4
8 1 22
5 5 3
4 2 3
1 1 1

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

45
1
2
3

Примечание

В первом примере для первого набора входных данных достижимы точки $$$(0, 0)$$$, $$$(1, 0)$$$, $$$(0, 1)$$$, $$$(2, 0)$$$, $$$(1, 1)$$$, $$$(0, 2)$$$, $$$(3, 0)$$$, $$$(2, 1)$$$, $$$(1, 2)$$$, $$$(0, 3)$$$, $$$(1, 3)$$$, $$$(0, 4)$$$.