Брюс Уэйн гонится за помощником Фальконе по прозвищу Пингвин на бэтмобиле по плоскости.
Из-за взрыва бэтмобиль повреждается и теперь может перемещаться только на один вперед и на один вправо. При этом, движение прямо тратит $$$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 | первая ошибка |
33 2 91 4 171 1 8
12 50 45
48 1 225 5 34 2 31 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)$$$.