题目描述

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

你可以进行如下的两步操作任意次（可以为零次）：

1. 首先，从集合 $S$ 中选择一个数 $x$，要求在 $S$ 中至少有 $k$ 个 $x$ 的倍数（包括 $x$ 本身）；
2. 然后，将 $x$ 从 $S$ 中移除（注意，其他元素不变）。

请你求出最多可以进行多少次这样的操作。

输入格式

每组测试数据包含多组测试用例。输入的第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。接下来每组测试用例一行，包含三个整数 $l$、$r$ 和 $k$（$1\le l\le r\leq 10^9$，$1\leq k\le r-l+1$），分别表示集合 $S$ 的最小值、最大值和参数 $k$。

输出格式

对于每组测试用例，输出一个整数，表示最多可以进行多少次操作。

说明/提示

在第一个测试用例中，初始时 $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$，除了 $x$ 本身外，$S$ 中都找不到 $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\}$。

由 ChatGPT 4.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

2
6
0
4
0
1
7148
500000000