28623번 - В погоне за Пингвином 다국어

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

Из-за взрыва бэтмобиль повреждается и теперь может перемещаться только на один вперед и на один вправо. При этом, движение прямо тратит $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$).

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

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