Dany jest dodatnia liczba całkowita $k$ oraz zbiór $S$ zawierający wszystkie liczby całkowite od $l$ do $r$ (włącznie).

Możesz wykonać następującą dwuetapową operację dowolną liczbę razy (być może zero):

1. Najpierw wybierz liczbę $x$ ze zbioru $S$ taką, że w zbiorze $S$ znajduje się co najmniej $k$ wielokrotności liczby $x$ (wliczając w to samą liczbę $x$);
2. Następnie usuń $x$ ze zbioru $S$ (zauważ, że nic innego nie jest usuwane).

Znajdź maksymalną możliwą liczbę operacji, które można wykonać.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę przypadków testowych. Następnie następuje opis przypadków testowych.

Jedyna linia każdego przypadku testowego zawiera trzy liczby całkowite $l$, $r$ oraz $k$ ($1 \le l \le r \le 10^9$, $1 \le k \le r - l + 1$) — odpowiednio minimalną liczbę całkowitą w $S$, maksymalną liczbę całkowitą w $S$ oraz parametr $k$.

Wyjście

Dla każdego przypadku testowego wyprowadź pojedynczą liczbę całkowitą — maksymalną możliwą liczbę operacji, które można wykonać.

Przykład

Wejście 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

Wyjście 1

2
6
0
4
0
1
7148
500000000

Uwagi

W pierwszym przypadku testowym początkowo $S = \{3, 4, 5, 6, 7, 8, 9\}$. Jedna z możliwych optymalnych sekwencji operacji to:

1. Wybierz $x = 4$ dla pierwszej operacji, ponieważ w $S$ są dwie wielokrotności liczby 4: 4 oraz 8. $S$ staje się równe $\{3, 5, 6, 7, 8, 9\}$;
2. Wybierz $x = 3$ dla drugiej operacji, ponieważ w $S$ są trzy wielokrotności liczby 3: 3, 6 oraz 9. $S$ staje się równe $\{5, 6, 7, 8, 9\}$.

W drugim przypadku testowym początkowo $S = \{4, 5, 6, 7, 8, 9\}$. Jedna z możliwych optymalnych sekwencji operacji to:

1. Wybierz $x = 5$, $S$ staje się równe $\{4, 6, 7, 8, 9\}$;
2. Wybierz $x = 6$, $S$ staje się równe $\{4, 7, 8, 9\}$;
3. Wybierz $x = 4$, $S$ staje się równe $\{7, 8, 9\}$;
4. Wybierz $x = 8$, $S$ staje się równe $\{7, 9\}$;
5. Wybierz $x = 7$, $S$ staje się równe $\{9\}$;
6. Wybierz $x = 9$, $S$ staje się równe $\{\}$.

W trzecim przypadku testowym początkowo $S = \{7, 8, 9\}$. Dla każdego $x$ w $S$ nie można znaleźć w $S$ żadnej wielokrotności $x$ poza nim samym. Ponieważ $k = 2$, nie można wykonać żadnych operacji.

W czwartym przypadku testowym początkowo $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Jedna z możliwych optymalnych sekwencji operacji to:

1. Wybierz $x = 2$, $S$ staje się równe $\{3, 4, 5, 6, 7, 8, 9, 10\}$;
2. Wybierz $x = 4$, $S$ staje się równe $\{3, 5, 6, 7, 8, 9, 10\}$;
3. Wybierz $x = 3$, $S$ staje się równe $\{5, 6, 7, 8, 9, 10\}$;
4. Wybierz $x = 5$, $S$ staje się równe $\{6, 7, 8, 9, 10\}$.