On vous donne un entier positif $k$ et un ensemble $S$ contenant tous les entiers de $l$ à $r$ (inclus).

Vous pouvez effectuer l'opération en deux étapes suivante un nombre quelconque de fois (éventuellement zéro) :

1. D'abord, choisissez un nombre $x$ dans l'ensemble $S$, tel qu'il y ait au moins $k$ multiples de $x$ dans $S$ (en incluant $x$ lui-même) ;
2. Ensuite, retirez $x$ de $S$ (notez que rien d'autre n'est retiré).

Trouvez le nombre maximum possible d'opérations pouvant être effectuées.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un entier unique $t$ ($1 \le t \le 10^4$) — le nombre de cas de test. La description des cas de test suit.

La seule ligne de chaque cas de test contient trois entiers $l$, $r$ et $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$) — l'entier minimum dans $S$, l'entier maximum dans $S$, et le paramètre $k$.

Sortie

Pour chaque cas de test, affichez un entier unique — le nombre maximum possible d'opérations pouvant être effectuées.

Exemples

Entrée 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

Sortie 1

2
6
0
4
0
1
7148
500000000

Remarque

Dans le premier cas de test, initialement, $S = \{3, 4, 5, 6, 7, 8, 9\}$. Une séquence optimale possible d'opérations est :

1. Choisir $x = 4$ pour la première opération, car il y a deux multiples de 4 dans $S$ : 4 et 8. $S$ devient égal à $\{3, 5, 6, 7, 8, 9\}$ ;
2. Choisir $x = 3$ pour la deuxième opération, car il y a trois multiples de 3 dans $S$ : 3, 6 et 9. $S$ devient égal à $\{5, 6, 7, 8, 9\}$.

Dans le deuxième cas de test, initialement, $S = \{4, 5, 6, 7, 8, 9\}$. Une séquence optimale possible d'opérations est :

1. Choisir $x = 5$, $S$ devient égal à $\{4, 6, 7, 8, 9\}$ ;
2. Choisir $x = 6$, $S$ devient égal à $\{4, 7, 8, 9\}$ ;
3. Choisir $x = 4$, $S$ devient égal à $\{7, 8, 9\}$ ;
4. Choisir $x = 8$, $S$ devient égal à $\{7, 9\}$ ;
5. Choisir $x = 7$, $S$ devient égal à $\{9\}$ ;
6. Choisir $x = 9$, $S$ devient égal à $\{\}$.

Dans le troisième cas de test, initialement, $S = \{7, 8, 9\}$. Pour chaque $x$ dans $S$, aucun multiple de $x$ autre que $x$ lui-même ne peut être trouvé dans $S$. Comme $k = 2$, vous ne pouvez effectuer aucune opération.

Dans le quatrième cas de test, initialement, $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Une séquence optimale possible d'opérations est :

1. Choisir $x = 2$, $S$ devient égal à $\{3, 4, 5, 6, 7, 8, 9, 10\}$ ;
2. Choisir $x = 4$, $S$ devient égal à $\{3, 5, 6, 7, 8, 9, 10\}$ ;
3. Choisir $x = 3$, $S$ devient égal à $\{5, 6, 7, 8, 9, 10\}$ ;
4. Choisir $x = 5$, $S$ devient égal à $\{6, 7, 8, 9, 10\}$.