Một đa tập hợp (multiset) là một tập hợp cho phép các phần tử lặp lại giá trị.

Gấu Panda có một đa tập hợp số nguyên ~S~ và ba số nguyên ~n, k, m~. Ban đầu, ~S = \{1, 2, \dots, n\}~. Panda muốn thực hiện một chuỗi các thao tác trên ~S~.

Trong mỗi thao tác:

• Chọn một tập con các số nguyên từ ~S~ hiện tại sao cho ước chung lớn nhất (GCD) của tất cả các số nguyên trong tập con được chọn đúng bằng ~k~.

• Xóa tất cả các số nguyên đã chọn khỏi ~S~.

Mỗi thao tác bắt buộc phải chọn ít nhất một số nguyên. Ước chung lớn nhất (GCD) của một tập hợp các số nguyên là số nguyên dương lớn nhất ~g~ chia hết mọi số nguyên trong tập hợp đó. Ví dụ: ~\gcd(12, 16) = 4~, ~\gcd(6, 9, 12) = 3~, và ~\gcd(6, 10, 15) = 1~. Lưu ý rằng GCD của một tập hợp chỉ gồm duy nhất một số nguyên chính là giá trị của số nguyên đó.

Trước khi thực hiện thao tác đầu tiên, Panda có thể chọn tối đa ~m~ số nguyên trong ~S~ và thay đổi giá trị của chúng. Mỗi số nguyên được chọn có thể đổi thành bất kỳ giá trị nào từ ~1~ đến ~n~. Lưu ý rằng việc sửa đổi này có thể khiến ~S~ chứa các phần tử có giá trị trùng lặp.

Bạn hãy giúp Panda tìm số lượng thao tác tối đa mà cậu có thể thực hiện thành công.

Input

Dòng đầu tiên chứa một số nguyên ~T~ (~1 \le T \le 10^4~) — số lượng bộ dữ liệu kiểm tra (test case).

Mỗi test case gồm một dòng duy nhất chứa ba số nguyên ~n, k, m~ (~1 \le k \le n \le 10^{18}~, ~0 \le m \le n~).

Output

Với mỗi test case, in ra trên một dòng một số nguyên duy nhất — số lượng thao tác tối đa có thể thực hiện thành công.

Sample Input 1

2
4 1 0
5 3 1

Sample Output 1

2
2

Notes

Giải thích ví dụ 1: Với ~n = 4, k = 1, m = 0~, có thể thực hiện ~2~ thao tác:

1. Chọn tập con ~\{1, 4\}~ (có ~\gcd(1, 4) = 1~) và xóa khỏi ~S~.

2. Chọn tập con ~\{2, 3\}~ (có ~\gcd(2, 3) = 1~) và xóa khỏi ~S~.

Giải thích ví dụ 2: Với ~n = 5, k = 3, m = 1~, đổi số ~1~ thành ~3~, sau đó thực hiện ~2~ thao tác:

1. Chọn tập con ~\{3\}~ (có ~\gcd(3) = 3~) và xóa khỏi ~S~.

2. Chọn tập con ~\{3\}~ (có ~\gcd(3) = 3~) và xóa khỏi ~S~.

Ràng buộc:

• Subtask 1 (~30\%~ số điểm): ~n \le 10^5~.

• Subtask 2 (~30\%~ số điểm): ~n \le 10^9~.

• Subtask 3 (~40\%~ số điểm): Không có ràng buộc gì thêm.