← 返回题目列表

Codeforces · 2029/A

A. 设置

中文机器翻译题面 查看原题

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

您可以执行以下两步操作任意次数(可能为零):

1.首先,从集合$$$S$$$中选择一个数$$$x$$$,使得$$$S$$$中至少有$$$k$$$个$$$x$$$的倍数(包括$$$x$$$本身);
2. 然后,从 $$$S$$$ 中删除 $$$x$$$(请注意,没有删除任何其他内容)。

找出可以执行的最大可能操作数。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$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$$$ 中的最小整数、$$$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$$$,除了$$$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\}$$$。