给定一个正整数 $k$ 和一个包含从 $l$ 到 $r$（包含 $l$ 和 $r$）的所有整数的集合 $S$。

你可以执行以下两步操作任意次数（可能为零次）：

1. 首先，从集合 $S$ 中选择一个数 $x$，使得 $S$ 中至少有 $k$ 个 $x$ 的倍数（包含 $x$ 本身）；
2. 然后，从 $S$ 中移除 $x$（注意，除了 $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\}$。