给定一个正整数 $$$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\}$$$。