양의 정수 $k$와 $l$부터 $r$까지의 모든 정수를 포함하는 집합 $S$가 주어집니다. 당신은 다음 두 단계로 이루어진 연산을 원하는 횟수만큼(0번 포함) 수행할 수 있습니다.

1. 먼저, 집합 $S$에서 $x$의 배수가 $k$개 이상 존재하는(자기 자신 포함) 수 $x$를 $S$에서 선택합니다.
2. 그 후, $S$에서 $x$를 제거합니다(다른 것은 제거되지 않습니다).

수행할 수 있는 최대 연산 횟수를 구하세요.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수 $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\}$입니다. $S$에 있는 각 $x$에 대해, $x$ 자신 외에 $S$에서 찾을 수 있는 $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\}$이 됩니다.