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.
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 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.
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.
| Subtask | Points | Additional Constraints | Necessary Subtasks | Checking Information |
| 1 | 15 | $$$t \leqslant 5$$$, $$$a_i, b_i, s_i \leqslant 10$$$ | – | full |
| 2 | 15 | $$$t \leqslant 100$$$, $$$a_i, b_i, s_i \leqslant 100$$$ for all $$$i$$$ | 1 | full |
| 3 | 14 | $$$s_i$$$ is divisible by $$$a_i$$$ and $$$b_i$$$ for all $$$i$$$ | – | full |
| 4 | 20 | $$$a_i \geqslant 10^5$$$ | – | full |
| 5 | 18 | $$$a_i = 1$$$ for all $$$i$$$ | – | full |
| 6 | 18 | none | 1 – 5 | first error |
33 2 91 4 171 1 8
12 50 45
48 1 225 5 34 2 31 1 1
45 1 2 3
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)$$$.
