A. Множество
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано натуральное число $$$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\leq 10^9$$$, $$$1\leq k\le r-l+1$$$) — минимальное число в $$$S$$$, максимальное число в $$$S$$$ и параметр $$$k$$$.

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

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

Пример
Входные данные
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
Выходные данные
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\}$$$.