Problem Description

Little Y and Little Z are both elves living in Arcaea Offline. Little Y has infinitely many fallen leaves, where the value of the $i$-th leaf is $C_i$. Little Z has infinitely many snowflakes, where the value of the $i$-th snowflake is $E_i$. After careful observation by Little X, he found that $C$ and $E$ satisfy special conditions:

$$C_i= \begin{cases} x\times i& (x\times i\le K)\\ -K& \text{otherwise} \end{cases}$$$$E_i= \begin{cases} y\times i& (y\times i\le K)\\ -K& \text{otherwise} \end{cases}$$

Little Y and Little Z can perform some operations on these leaves and snowflakes. Each time, they choose one leaf and one snowflake whose sum of values is $\ge K$, and then combine them into a colorful memory (Erinnerung). After that, this snowflake and this leaf disappear, and they cannot be used in later operations.

Little X wants to know the maximum number of operations they can perform.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain three non-negative integers $x,y,K$.

Output Format

For each test case, output one integer, representing the maximum number of operations. Output the answers for each test case on separate lines.

2
2 3 10
2 4 11

3
2

1
0 0 1

0

Hint

Sample Explanation

For the first test case of Sample 1, the values of the leaves are $2,4,6,8,10,-10,-10\dots$, and the values of the snowflakes are $3,6,9,-10,-10\dots$. In the first operation, choose the $4$-th leaf and the $1$-st snowflake, with sum $11$. In the second operation, choose the $2$-nd leaf and the $2$-nd snowflake, with sum $10$. In the third operation, choose the $5$-th leaf and the $3$-rd snowflake, with sum $19$. Thus, they can perform $3$ operations. It is easy to prove that there is no better solution.

For the second test case, two possible operations are: choosing the $4$-th leaf and the $1$-st snowflake, and choosing the $2$-nd leaf and the $2$-nd snowflake.

For Sample 2, all leaves and snowflakes have value $0$, so it is impossible to find a leaf and a snowflake with sum $\ge 1$.

---

Constraints

• Subtask 1 (30 points): $x,y,K,T\le 10$.
• Subtask 2 (70 points): No special constraints.

For $100\%$ of the testdata, $0\le x,y\le 10^{10}$, $1\le K\le 10^{10}$, $1\le T\le 10^5$.

Translated by ChatGPT 5