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)$.