my-solutions/codeforces/round-985/problem_a

A. Set

Codeforces

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):

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.

Input

Each test contains multiple test cases. The first line of the input contains a single integer t (1 ≤ t ≤ 104) — 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 ≤ l ≤ r ≤ 109, 1 ≤ k ≤ r − l + 1) — the minimum integer in S, the maximum integer in S, and the parameter k.

Output

For each test case, output a single integer — the maximum possible number of operations that can be performed.

Example

Input

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

Output

2
6
0
4
0
1
7148
500000000

Note

In 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}.