수 집합 (큰 입력)

연속한 정수로 이루어진 구간과 정수 $P$가 주어진다. 처음에는 구간 안의 정수가 각각 자기 혼자만 들어 있는 집합에 속한다.

구간 안의 모든 정수 쌍을 차례로 살펴본다. 두 정수의 공통 소인수 중에 $P$ 이상인 것이 하나라도 있으면, 두 정수가 속한 집합을 하나로 합친다.

이 과정이 끝났을 때 집합이 몇 개 남는지 구하라.

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

이어지는 $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$는 남은 집합의 개수이다.