# A. Set

[Codeforces](https://codeforces.com/contest/2029/problem/A)

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