Дано положительное целое число $k$ и множество $S$, состоящее из всех целых чисел от $l$ до $r$ включительно.

Вы можете выполнить следующую операцию, состоящую из двух шагов, любое количество раз (возможно, ноль):

1. Выбрать число $x$ из множества $S$ такое, что в $S$ есть по крайней мере $k$ кратных числа $x$ (включая само $x$);
2. Удалить $x$ из $S$ (заметьте, что больше ничего не удаляется).

Найдите максимально возможное количество операций, которые можно выполнить.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке входных данных содержится целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов.

Единственная строка каждого набора содержит три целых числа $l$, $r$ и $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$) — минимальное целое число в $S$, максимальное целое число в $S$ и параметр $k$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное количество операций, которые можно выполнить.

Примеры

Входные данные 1

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

Выходные данные 1

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\}$. Для каждого $x$ в $S$ в $S$ нет кратных числа $x$, кроме самого $x$. Поскольку $k = 2$, вы не можете выполнить ни одной операции.

В четвертом наборе входных данных изначально $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Одна из возможных оптимальных последовательностей операций:

1. Выбрать $x = 2$, $S$ становится равным $\{3, 4, 5, 6, 7, 8, 9, 10\}$;

2. Выбрать $x = 4$, $S$ становится равным $\{3, 5, 6, 7, 8, 9, 10\}$;

3. Выбрать $x = 3$, $S$ становится равным $\{5, 6, 7, 8, 9, 10\}$;

4. Выбрать $x = 5$, $S$ становится равным $\{6, 7, 8, 9, 10\}$.