給定一個正整數 $k$ 以及一個包含從 $l$ 到 $r$（包含 $l$ 與 $r$）所有整數的集合 $S$。

你可以執行以下兩步驟操作任意次數（可能為零次）：

1. 首先，從集合 $S$ 中選擇一個數字 $x$，使得在 $S$ 中至少有 $k$ 個 $x$ 的倍數（包含 $x$ 本身）；
2. 然後，將 $x$ 從 $S$ 中移除（注意除了 $x$ 之外沒有其他元素被移除）。

請找出可以執行的最大操作次數。

輸入格式

每個測試包含多個測試案例。輸入的第一行包含一個單一整數 $t$ ($1 \le t \le 10^4$)，代表測試案例的數量。接著是各個測試案例的描述。

每個測試案例僅包含一行，包含三個整數 $l$、$r$ 和 $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$)，分別代表 $S$ 中的最小整數、最大整數以及參數 $k$。

輸出格式

對於每個測試案例，輸出一個單一整數，代表可以執行的最大操作次數。

範例

輸入格式 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

輸出格式 1

2
6
0
4
0
1
7148
500000000

說明

在第一個測試案例中，初始時 $S = \{3, 4, 5, 6, 7, 8, 9\}$。一種可能的最佳操作序列為：

1. 選擇 $x = 4$ 進行第一次操作，因為在 $S$ 中有兩個 4 的倍數：4 和 8。$S$ 變為 $\{3, 5, 6, 7, 8, 9\}$；
2. 選擇 $x = 3$ 進行第二次操作，因為在 $S$ 中有三個 3 的倍數：3、6 和 9。$S$ 變為 $\{5, 6, 7, 8, 9\}$。

在第二個測試案例中，初始時 $S = \{4, 5, 6, 7, 8, 9\}$。一種可能的最佳操作序列為：

1. 選擇 $x = 5$，$S$ 變為 $\{4, 6, 7, 8, 9\}$；
2. 選擇 $x = 6$，$S$ 變為 $\{4, 7, 8, 9\}$；
3. 選擇 $x = 4$，$S$ 變為 $\{7, 8, 9\}$；
4. 選擇 $x = 8$，$S$ 變為 $\{7, 9\}$；
5. 選擇 $x = 7$，$S$ 變為 $\{9\}$；
6. 選擇 $x = 9$，$S$ 變為 $\{\}$。

在第三個測試案例中，初始時 $S = \{7, 8, 9\}$。對於 $S$ 中的每個 $x$，在 $S$ 中找不到除了 $x$ 本身以外的 $x$ 的倍數。由於 $k = 2$，你無法執行任何操作。

在第四個測試案例中，初始時 $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$。一種可能的最佳操作序列為：

1. 選擇 $x = 2$，$S$ 變為 $\{3, 4, 5, 6, 7, 8, 9, 10\}$；
2. 選擇 $x = 4$，$S$ 變為 $\{3, 5, 6, 7, 8, 9, 10\}$；
3. 選擇 $x = 3$，$S$ 變為 $\{5, 6, 7, 8, 9, 10\}$；
4. 選擇 $x = 5$，$S$ 變為 $\{6, 7, 8, 9, 10\}$。