수의 집합

연속된 정수의 수열로 시작한다. 이들을 집합으로 묶으려고 한다.

구간과 정수 P가 주어진다. 처음에는 구간의 각 수가 각각 별도의 집합에 속한다.

그런 다음 구간에 있는 정수의 각 쌍을 고려한다. 두 정수가 적어도 P인 소인수를 공유하면, 두 정수가 속한 두 집합을 합친다.

이 과정이 끝났을 때 서로 다른 집합이 몇 개 존재하는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ C ≤ 10 1 ≤ A ≤ B ≤ 1000 2 ≤ P ≤ B

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ C ≤ 100 1 ≤ A ≤ B ≤ $10^{12}$ B ≤ A + 1000000 2 ≤ P ≤ B

입력 파일의 테스트 케이스 수인 정수 C를 포함하는 한 줄이 주어진다.

각 테스트 케이스마다 공백 하나로 구분된 세 정수 A, B, P를 포함하는 한 줄이 주어진다. A와 B는 각각 구간의 처음 정수와 마지막 정수이며, P는 위에서 설명한 수이다.

각 테스트 케이스마다 문자열 "Case #X: Y"을 포함하는 한 줄을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 집합의 개수이다.