题目描述

你已经盯着电脑屏幕太久了；是时候让它休息一下，去摸摸草了。

你的屏幕是一条长度为 $a$ 的线段，上面显示着 $n$ 个标签页（tab）。你想通过点击每个标签页右端点的 $x$ 来关闭所有标签页。

每个标签页的长度为

$$\text{len} = \min\left(b,\frac{a}{m}\right)$$

其中 $m$ 是当前仍然存在的标签页数量。所有标签页始终从屏幕左端开始连续紧密排列；也就是说，这些 $x$ 的位置分别在距离左端

$$\text{len},\ 2\cdot \text{len},\ 3\cdot \text{len},\ \ldots,\ m\cdot \text{len} $$

处。

请注意，随着你不断关闭标签页，每个标签页的长度都会改变。

现在你的鼠标光标位于屏幕的最左端，你想知道：为了关闭所有标签页，你最少需要移动鼠标多少次？

如果你难以理解题意，你也可以参考浏览器标签页的可视化示例，或点击 样例模拟器 进行模拟测试。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 一行输入三个空格隔开的整数 $a,b,n$。

输出格式

对于每一组数据，输出一个整数表示答案。

12
8 1 6
9 6 2
10 3 1
10 1 10
9 2 1
5 5 6
6 2 7
9 1 9
3 2 6
8 1 7
8 1 9
8 2 4

1
2
1
1
1
1
2
1
2
1
2
1

样例 1 解释

在第一组数据中，一种可行的操作方式是：把光标移动到 $1$ 的位置，然后点击 $6$ 次。

在第二组数据中，一种可行的操作方式是：先把光标移动到 $4.5$，点击一次；然后再移动到 $6$，再点击一次。可以证明，不可能用少于 $2$ 次移动来关闭所有标签页。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 10^4$，$1\leq b\leq a\leq 10^9$，$1\leq n\leq 10^9$。

• 子任务 1（$30$ 分）：保证 $n\leq 2$。
• 子任务 2（$30$ 分）：保证 $b=a$。
• 子任务 3（$40$ 分）：无特殊限制。