P7441 "EZEC-7" Erinnerung

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.

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

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

**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