You've been staring at your computer screen for too long; it is time to give it a break and go touch some grass.

Your screen is a line of length $a$, and there are $n$ tabs displayed on it. You want to close all of the tabs by clicking on the x's at their right endpoint.

Every tab is a segment of length $\textrm{len}=\min(b,\frac{a}{m})$, where $m$ is the number of remaining tabs. The tabs are always tightly arranged in sequence from the left endpoint of the screen; that is, the x's will be at $\textrm{len},2\cdot \textrm{len},3\cdot \textrm{len},\ldots,m\cdot\textrm{len}$ units away from the left endpoint. Please note that the length of each tab will change as you are closing tabs.

Now your cursor is at the left endpoint of the screen. You wonder what the minimum number of times you need to move the mouse to close all tabs is.

If you have difficulty understanding the statement, you may also refer to your browser tab for a visualization, or click here.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case is a line of three integers $a$, $b$, and $n$ ($1\le b\le a \le 10^9$, $1\le n \le 10^9$).

Output

For each test case, output a single integer — the minimum number of times you need to move the mouse to close all tabs.

Note

In the first test case, a possible course of action is to move your cursor to $1$ and press $6$ times.

In the second test case, a possible course of action is to move your cursor to $4.5$ and press once, then move it to $6$ and press again. It can be proved that the tabs cannot be closed with less than $2$ moves.

Samples

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