1901: Set

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：65 解决：14

题目描述

给你一个正整数k和一个有l至r的所有整数组成的集合S。

你可以执行一下两步运算的任意次数(可能为0)：

1.首先，从集合S中选择一个数字x，使得S中至少有k个x的倍数(包括x本身)：

2.然后，从S中删除x(注意没有删除其他任何内容)；

求可以进行的最大操作数。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 t.(1≤t≤104 ) - 测试用例的数量。测试用例说明如下。

每个测试用例的唯一一行包含三个整数l,r 和k(1<=l<=r<=109 ).(1<=k<=r-l+1)--最小整数，最大整数和参数k。

输出

对于每个测试用例，输出一个整数，可执行的最大操作数。

样例输入 复制 

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

提示

注

在第一个测试用例中，最初是 。一个可能的最佳操作顺序是

  1. 选择 
     进行第一次操作，因为在  中有两个 4的倍数： 4 和 8。 S 就等于 
     ；
  2. 选择 
     进行第二次运算，因为 中有 3 的三个倍数：  、6和 9 。 就等于  。

在第二个测试案例中，起初是  。一个可能的最佳操作序列是

  1. 选择 ,S 变为等于  ；
  2. 选择  , 等于 ；
  3. 选择  , 变为  ；
  4. 选择  ， S 就等于  ；
  5. 选择  , 变为等于  ；
  6. 选择 ， 就等于  。

在第三个测试案例中，最初选择 。对于  中的每一个  ， 中除了 本身之外，找不到  的倍数。自 起，无法进行任何运算。

在第四个测试用例中，最初是  。一个可能的最佳操作序列是

  1. 选择 ， 变为等于  ；
  2. 选择 
     , 等于  
  3. 选择 就等于 ；
  4. 选择  就等于 。