题目描述

小 Y 和小 Z 都是生活在 Arcaea Offline 的精灵。小 Y 有无数片落叶，其中第 $i$ 片落叶的价值为 $C_i$。小 Z 有无数片雪花，其中第 $i$ 片雪花的价值为 $E_i$。经过小 X 的仔细观察，他发现 $C$ 和 $E$ 满足特殊的条件：

$$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} $$

小 Y 和小 Z 可以对这些落叶和雪花进行一些操作。每次，他们会选择满足价值之和 $\ge K$ 的一片落叶和一片雪花，然后让把它们一同组成一段彩色的回忆（Erinnerung）。之后，这片雪花和这片落叶就消失不见了，之后的操作也不能再用到这片雪花和落叶了。

小 X 想知道，他们最多能进行多少次操作。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行三个非负整数 $x,y,K$。

输出格式

对于每组数据，输出一个整数，代表最多能有多少次操作。每组数据的答案用一个换行符隔开。

2
2 3 10
2 4 11

3
2

1
0 0 1

0

提示

【样例解释】

对于样例 1 的第一组数据，落叶的价值为 $2,4,6,8,10,-10,-10\dots$ ，雪花的价值为 $3,6,9,-10,-10\dots$ 。第一次操作选取第 $4$ 片落叶和第 $1$ 片雪花，价值和为 $11$。第二次操作选取第 $2$ 片落叶和第 $2$ 片雪花，价值和为 $10$。第三次操作选取第 $5$ 片落叶和第 $3$ 片雪花，价值和为 $19$。如是，可以进行 $3$ 次操作。容易证明不存在更优的解。

对于第二组数据，进行的两次操作可以为：选取第 $4$ 片落叶和第 $1$ 片雪花，以及选取第 $2$ 片落叶和第 $2$ 片雪花。

对于样例 2，所有的雪花和落叶的价值都为 $0$，不可能找到落叶和雪花使其和 $\ge 1$。

---

【数据范围】

• Subtask 1（30 points）：$x,y,K,T\le 10$。
• Subtask 2（70 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $0\le x,y\le 10^{10}$，$1\le K\le 10^{10}$，$1\le T\le 10^5$。