Bạn được cho một số nguyên dương $k$ và một tập hợp $S$ gồm tất cả các số nguyên từ $l$ đến $r$ (bao gồm cả $l$ và $r$).

Bạn có thể thực hiện thao tác hai bước sau đây bất kỳ số lần nào (có thể là không lần nào):

1. Đầu tiên, chọn một số $x$ từ tập hợp $S$, sao cho có ít nhất $k$ bội số của $x$ nằm trong $S$ (bao gồm cả chính $x$);
2. Sau đó, loại bỏ $x$ khỏi $S$ (lưu ý rằng không có phần tử nào khác bị loại bỏ).

Hãy tìm số lượng thao tác tối đa có thể thực hiện được.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Các bộ dữ liệu tiếp theo được mô tả như sau.

Dòng duy nhất của mỗi bộ dữ liệu chứa ba số nguyên $l$, $r$ và $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$) — số nguyên nhỏ nhất trong $S$, số nguyên lớn nhất trong $S$ và tham số $k$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra một số nguyên duy nhất — số lượng thao tác tối đa có thể thực hiện được.

Ví dụ

Dữ liệu vào 1

8
3 9 2
4 9 1
7 9 2
2 10 2
154 220 2
147 294 2
998 24435 3
1 1000000000 2

Dữ liệu ra 1

2
6
0
4
0
1
7148
500000000

Ghi chú

Trong bộ dữ liệu đầu tiên, ban đầu $S = \{3, 4, 5, 6, 7, 8, 9\}$. Một chuỗi thao tác tối ưu có thể là:

1. Chọn $x = 4$ cho thao tác đầu tiên, vì có hai bội số của 4 trong $S$: 4 và 8. $S$ trở thành $\{3, 5, 6, 7, 8, 9\}$;
2. Chọn $x = 3$ cho thao tác thứ hai, vì có ba bội số của 3 trong $S$: 3, 6 và 9. $S$ trở thành $\{5, 6, 7, 8, 9\}$.

Trong bộ dữ liệu thứ hai, ban đầu $S = \{4, 5, 6, 7, 8, 9\}$. Một chuỗi thao tác tối ưu có thể là:

1. Chọn $x = 5$, $S$ trở thành $\{4, 6, 7, 8, 9\}$;
2. Chọn $x = 6$, $S$ trở thành $\{4, 7, 8, 9\}$;
3. Chọn $x = 4$, $S$ trở thành $\{7, 8, 9\}$;
4. Chọn $x = 8$, $S$ trở thành $\{7, 9\}$;
5. Chọn $x = 7$, $S$ trở thành $\{9\}$;
6. Chọn $x = 9$, $S$ trở thành $\{\}$.

Trong bộ dữ liệu thứ ba, ban đầu $S = \{7, 8, 9\}$. Với mỗi $x$ trong $S$, không có bội số nào của $x$ ngoài chính nó có thể tìm thấy trong $S$. Vì $k = 2$, bạn không thể thực hiện thao tác nào.

Trong bộ dữ liệu thứ tư, ban đầu $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Một chuỗi thao tác tối ưu có thể là:

1. Chọn $x = 2$, $S$ trở thành $\{3, 4, 5, 6, 7, 8, 9, 10\}$;
2. Chọn $x = 4$, $S$ trở thành $\{3, 5, 6, 7, 8, 9, 10\}$;
3. Chọn $x = 3$, $S$ trở thành $\{5, 6, 7, 8, 9, 10\}$;
4. Chọn $x = 5$, $S$ trở thành $\{6, 7, 8, 9, 10\}$.