题目描述

给定一个正整数 ( k ) 和一个集合 ( S )，其中 ( S ) 是从 ( l ) 到 ( r )（包含 ( l ) 和 ( r )）的所有整数。

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

1. 从集合 ( S ) 中选择一个数字 ( x )，使得 ( S ) 中有至少 ( k ) 个 ( x ) 的倍数（包括 ( x ) 本身）。
2. 然后，从集合 ( S ) 中移除 ( x ) （注意，仅仅移除 ( x )，其他数字不变）。

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

输入格式

• 每个测试包含多个案例。
• 第一行包含一个整数 t (1 <=t<= 10^4 ），表示测试案例的数量。
• 接下来每个测试案例包含三个整数 l , r, 和 k ,1<=l <=r <=10^9 ,1<=k <=r-l+1 ——表示集合 ( S ) 中的最小值 ( l )、最大值 ( r ) 和参数 ( 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

提示

在第一个测试案例中，初始时，( 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 ) 中，因此不能执行任何操作。