题目描述

屏幕是长度为 $a$ 的一条线段，上面有 $n$ 个标签（tabs）并排显示。你要通过点击每个标签右端的小叉（$x$）来关闭所有标签。

当前剩余标签的数量为 $m$ 时，每个标签的长度为 $\min(b, \frac{a}{m})$（记作 $\text{len}=\min(b, \frac{a}{m})$）。标签始终从屏幕左端紧密排列，因此所有小叉的位置相对于左端分别是 $\text{len},2\cdot\text{len},3\cdot\text{len},\dots,m\cdot\text{len}$。注意：随着你关闭标签，剩余标签数 $m$ 会减少，因而每次点击时标签长度与小叉位置都会发生变化。

你的鼠标初始位于屏幕左端。每次你可以把鼠标移动到任意位置，然后点击若干次（每次点击都关闭当前右端所对应的那个仍在屏幕上的标签）。问：关闭所有 $n$ 个标签，鼠标最少需要移动多少次？

备注：如果您难以理解该声明，您还可以参考浏览器选项卡进行可视化，或点击此处。

输入格式

• 第一行包含一个整数 $t$，表示测试用例个数（$1\le t\le 10^4$）。
• 接下来每个测试用例占一行，包含三个整数 $a,b,n$，满足 $1\le b\le a\le 10^9,1\le n\le 10^9$，分别表示屏幕长度、单个标签长度上限，以及一开始的标签个数。

输出格式

对于每个测试用例，输出一行，包含一个整数——关闭所有标签所需的最少移动次数。

样例输入

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

说明

样例解释

• 第一个样例：$a=8,b=1,n=6$。每个标签长度为 $\min(1,\frac{8}{6})=1$，所有小叉在 $1,2,3,4,5,6$ 位置。把鼠标移到 $1$，连续点击 $6$ 次即可一次性关闭全部标签，移动次数为 $1$。
• 第二个样例：$a=9,b=6,n=2$。可以先把鼠标移到 $4.5$（此时 $m=2$，$\text{len}=\min(6,\frac{9}{2})=4.5$），点击一次关闭右端第一个标签（对应位置 $4.5$），剩余一个标签时再移到其右端位置 $9$ 点击一次，总共移动 $2$ 次；可以证明不能更少。