Box Stacks

Nam có $n$ chiếc hộp giống hệt nhau. Khối lượng của mỗi chiếc hộp là $m$, và độ bền của mỗi chiếc hộp là $d$.

Để tiết kiệm không gian, Nam muốn xếp các chiếc hộp thành một số tháp bằng cách chồng chúng lên nhau. Mỗi tháp gồm một số nguyên dương các hộp được đặt chồng lên nhau. Để đảm bảo không có chiếc hộp nào bị hỏng, điều kiện sau phải được thỏa mãn:

• Đối với mỗi chiếc hộp, tổng khối lượng của tất cả các hộp nằm phía trên nó không được vượt quá độ bền của chiếc hộp đó.

Hãy giúp Nam tính toán số lượng tháp tối thiểu có thể đạt được, với điều kiện phải sử dụng tất cả $n$ chiếc hộp.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 10^4$) là số lượng bộ dữ liệu kiểm thử.

Mỗi bộ dữ liệu gồm một dòng chứa ba số nguyên $n$, $m$, và $d$ ($1 ≤ n, m, d ≤ 50$).

Kết quả

Đối với mỗi bộ dữ liệu, in ra một số nguyên là số lượng tháp tối thiểu.

Chấm điểm

Subtask 1 (30 points). $n, m, d ≤ 10$

Subtask 2 (30 points). $n, m, d ≤ 50$ với các tỷ lệ khối lượng và độ bền biên

Subtask 3 (40 points). $1 ≤ t ≤ 10^4$; $1 ≤ n, m, d ≤ 50$

Ví dụ

Input

1
6 2 5

Output

2

Ghi chú

Trong ví dụ này, có thể xếp thành hai tháp với số lượng hộp phù hợp để tổng khối lượng không vượt quá độ bền của bất kỳ hộp nào.