Se te da un entero positivo $k$ y un conjunto $S$ de todos los enteros desde $l$ hasta $r$ (inclusive).

Puedes realizar la siguiente operación de dos pasos cualquier número de veces (posiblemente cero):

1. Primero, elige un número $x$ del conjunto $S$, tal que haya al menos $k$ múltiplos de $x$ en $S$ (incluyendo al propio $x$).
2. Luego, elimina $x$ de $S$ (ten en cuenta que no se elimina nada más).

Encuentra el número máximo posible de operaciones que se pueden realizar.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único entero $t$ ($1 \le t \le 10^4$) — el número de casos de prueba. A continuación se describe cada caso de prueba.

La única línea de cada caso de prueba contiene tres enteros $l$, $r$ y $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$) — el entero mínimo en $S$, el entero máximo en $S$ y el parámetro $k$.

Salida

Para cada caso de prueba, imprime un único entero — el número máximo posible de operaciones que se pueden realizar.

Ejemplos

Entrada 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

Salida 1

2
6
0
4
0
1
7148
500000000

Nota

En el primer caso de prueba, inicialmente, $S = \{3, 4, 5, 6, 7, 8, 9\}$. Una posible secuencia óptima de operaciones es:

1. Elegir $x = 4$ para la primera operación, ya que hay dos múltiplos de 4 en $S$: 4 y 8. $S$ se convierte en $\{3, 5, 6, 7, 8, 9\}$.
2. Elegir $x = 3$ para la segunda operación, ya que hay tres múltiplos de 3 en $S$: 3, 6 y 9. $S$ se convierte en $\{5, 6, 7, 8, 9\}$.

En el segundo caso de prueba, inicialmente, $S = \{4, 5, 6, 7, 8, 9\}$. Una posible secuencia óptima de operaciones es:

1. Elegir $x = 5$, $S$ se convierte en $\{4, 6, 7, 8, 9\}$.
2. Elegir $x = 6$, $S$ se convierte en $\{4, 7, 8, 9\}$.
3. Elegir $x = 4$, $S$ se convierte en $\{7, 8, 9\}$.
4. Elegir $x = 8$, $S$ se convierte en $\{7, 9\}$.
5. Elegir $x = 7$, $S$ se convierte en $\{9\}$.
6. Elegir $x = 9$, $S$ se convierte en $\{\}$.

En el tercer caso de prueba, inicialmente, $S = \{7, 8, 9\}$. Para cada $x$ en $S$, no se puede encontrar ningún múltiplo de $x$ en $S$ que no sea el propio $x$. Dado que $k = 2$, no puedes realizar ninguna operación.

En el cuarto caso de prueba, inicialmente, $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Una posible secuencia óptima de operaciones es:

1. Elegir $x = 2$, $S$ se convierte en $\{3, 4, 5, 6, 7, 8, 9, 10\}$.
2. Elegir $x = 4$, $S$ se convierte en $\{3, 5, 6, 7, 8, 9, 10\}$.
3. Elegir $x = 3$, $S$ se convierte en $\{5, 6, 7, 8, 9, 10\}$.
4. Elegir $x = 5$, $S$ se convierte en $\{6, 7, 8, 9, 10\}$.