수의 집합 (Large)

연속한 정수를 다음 절차에 따라 여러 집합으로 나눈다.

먼저 대상이 되는 정수 구간과 정수 $P$가 주어진다. 처음에는 구간의 정수마다 그 정수 하나만 담은 집합이 따로 있다. 이제 구간에 속한 두 정수의 모든 쌍을 살펴보면서, 두 정수에 공통인 $P$ 이상의 소인수가 있으면 두 정수가 속한 집합을 하나로 합친다.

이 절차가 끝났을 때 집합은 몇 개인가?

첫 줄에 테스트 케이스의 수 $C$가 주어진다.

각 테스트 케이스는 한 줄이며, 공백으로 구분된 세 정수 $A$, $B$, $P$가 주어진다. $A$와 $B$는 각각 구간의 첫 정수와 마지막 정수이고, $P$는 위에서 설명한 수다.

제약

• $1 \le C \le 100$
• $1 \le A \le B \le 10^{12}$
• $B \le A + 1000000$
• $2 \le P \le B$

각 테스트 케이스마다 Case #X: Y 형식의 한 줄을 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 집합의 개수다.