Monocarp has $n$ identical boxes. The weight of each box is $m$, and the durability of each box is $d$.

To save space, Monocarp wants to build several "towers" of boxes by stacking them on top of each other. Each tower will consist of a positive (greater than $0$) integer number of boxes stacked on top of each other. To ensure that no box breaks, the following condition must be met:

• for each box, the total weight of all boxes above it must not exceed the durability of that box.

Help Monocarp calculate the minimum number of towers he can achieve, given that each of the $n$ boxes must be used.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of a single line containing three integers $n, m, d$ ($1 \le n, m, d \le 50$).

Output

For each test case, print one integer — the minimum number of towers.

Note

In the first example, it is possible to build three towers consisting of $3$, $2$, and $3$ boxes, respectively.

In the second example, all boxes are durable enough to build one tower of $8$ boxes.

In the third example, the weight of the box exceeds its durability, so they cannot be stacked on top of each other. As a result, $5$ separate towers will have to be built.

Samples

3
8 10 20
8 1 20
5 3 2

3
1
5