A. In Pursuit of the Penguin
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bruce Wayne is chasing his assistant, known as the Penguin, on the Batmobile on a plane.

Due to an explosion, the Batmobile is damaged and can now only move one step forward and one step to the right. Moving straight consumes $$$a$$$ units of fuel, while moving to the right consumes $$$b$$$ units of fuel.

Currently, the superhero's car is located at point $$$(0, 0)$$$ and has $$$f$$$ units of fuel in the tank. When the fuel runs out, the Batmobile will no longer be able to move and the hero will have to chase the villain on foot.

Determine how many points with integer coordinates the Batman can still reach on his Batmobile.

As it is known, all superheroes usually exist in $$$t$$$ parallel universes. Therefore, solve this problem for each of the parallel universes.

Input

The first line of input contains an integer $$$t$$$ - the number of universes in which the problem needs to be solved ($$$1 \leqslant t \leqslant 500$$$).

Each of the following $$$t$$$ input lines describes one universe. The $$$i$$$-th line contains three integers $$$a_i$$$, $$$b_i$$$, and $$$f_i$$$ separated by a space - the fuel consumption for moving one step forward, the fuel consumption for moving one step to the right, and the initial fuel volume in the Batmobile's tank ($$$1 \leqslant a_i, b_i, f_i \leqslant 10^9$$$).

Output

Output the answer to the problem for each universe on a separate line. Each answer should consist of a single integer - the number of reachable points with the Batmobile.

Scoring

Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks, as well as the tests from the statement, are passed successfully.

SubtaskPoints Additional Constraints Necessary Subtasks Checking Information
115$$$t \leqslant 5$$$, $$$a_i, b_i, s_i \leqslant 10$$$–full
215$$$t \leqslant 100$$$, $$$a_i, b_i, s_i \leqslant 100$$$ for all $$$i$$$1full
314$$$s_i$$$ is divisible by $$$a_i$$$ and $$$b_i$$$ for all $$$i$$$–full
420$$$a_i \geqslant 10^5$$$–full
518$$$a_i = 1$$$ for all $$$i$$$–full
618none1 – 5first error
Examples
Input
3
3 2 9
1 4 17
1 1 8
Output
12
50
45
Input
4
8 1 22
5 5 3
4 2 3
1 1 1
Output
45
1
2
3
Note

In the first example, for the first set of input data, the reachable points are $$$(0, 0)$$$, $$$(1, 0)$$$, $$$(0, 1)$$$, $$$(2, 0)$$$, $$$(1, 1)$$$, $$$(0, 2)$$$, $$$(3, 0)$$$, $$$(2, 1)$$$, $$$(1, 2)$$$, $$$(0, 3)$$$, $$$(1, 3)$$$, $$$(0, 4)$$$.