A. Settime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a positive integer $$$k$$$ and a set $$$S$$$ of all integers from $$$l$$$ to $$$r$$$ (inclusive).You can perform the following two-step operation any number of times (possibly zero): First, choose a number $$$x$$$ from the set $$$S$$$, such that there are at least $$$k$$$ multiples of $$$x$$$ in $$$S$$$ (including $$$x$$$ itself); Then, remove $$$x$$$ from $$$S$$$ (note that nothing else is removed).Find the maximum possible number of operations that can be performed.InputEach test contains multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of test cases follows.The only line of each test case contains three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$1\le l\le r\leq 10^9$$$, $$$1\leq k\le r-l+1$$$) — the minimum integer in $$$S$$$, the maximum integer in $$$S$$$, and the parameter $$$k$$$.OutputFor each test case, output a single integer — the maximum possible number of operations that can be performed.ExampleInput83 9 24 9 17 9 22 10 2154 220 2147 294 2998 24435 31 1000000000 2Output2
6
0
4
0
1
7148
500000000
NoteIn the first test case, initially, $$$S = \{3,4,5,6,7,8,9\}$$$. One possible optimal sequence of operations is: Choose $$$x = 4$$$ for the first operation, since there are two multiples of $$$4$$$ in $$$S$$$: $$$4$$$ and $$$8$$$. $$$S$$$ becomes equal to $$$\{3,5,6,7,8,9\}$$$; Choose $$$x = 3$$$ for the second operation, since there are three multiples of $$$3$$$ in $$$S$$$: $$$3$$$, $$$6$$$, and $$$9$$$. $$$S$$$ becomes equal to $$$\{5,6,7,8,9\}$$$. In the second test case, initially, $$$S=\{4,5,6,7,8,9\}$$$. One possible optimal sequence of operations is: Choose $$$x = 5$$$, $$$S$$$ becomes equal to $$$\{4,6,7,8,9\}$$$; Choose $$$x = 6$$$, $$$S$$$ becomes equal to $$$\{4,7,8,9\}$$$; Choose $$$x = 4$$$, $$$S$$$ becomes equal to $$$\{7,8,9\}$$$; Choose $$$x = 8$$$, $$$S$$$ becomes equal to $$$\{7,9\}$$$; Choose $$$x = 7$$$, $$$S$$$ becomes equal to $$$\{9\}$$$; Choose $$$x = 9$$$, $$$S$$$ becomes equal to $$$\{\}$$$. In the third test case, initially, $$$S=\{7,8,9\}$$$. For each $$$x$$$ in $$$S$$$, no multiple of $$$x$$$ other than $$$x$$$ itself can be found in $$$S$$$. Since $$$k = 2$$$, you can perform no operations.In the fourth test case, initially, $$$S=\{2,3,4,5,6,7,8,9,10\}$$$. One possible optimal sequence of operations is: Choose $$$x = 2$$$, $$$S$$$ becomes equal to $$$\{3,4,5,6,7,8,9,10\}$$$; Choose $$$x = 4$$$, $$$S$$$ becomes equal to $$$\{3,5,6,7,8,9,10\}$$$; Choose $$$x = 3$$$, $$$S$$$ becomes equal to $$$\{5,6,7,8,9,10\}$$$; Choose $$$x = 5$$$, $$$S$$$ becomes equal to $$$\{6,7,8,9,10\}$$$.