You 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):
Find the maximum possible number of operations that can be performed.
Each 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$$$.
For each test case, output a single integer — the maximum possible number of operations that can be performed.
83 9 24 9 17 9 22 10 2154 220 2147 294 2998 24435 31 1000000000 2
2 6 0 4 0 1 7148 500000000
In the first test case, initially, $$$S = \{3,4,5,6,7,8,9\}$$$. One possible optimal sequence of operations is:
In the second test case, initially, $$$S=\{4,5,6,7,8,9\}$$$. One possible optimal sequence of operations is:
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:
Name |
---|