수 집합

연속한 정수로 이루어진 구간이 주어진다. 이 정수들을 여러 집합으로 나눈다.

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

그다음 구간 안의 정수 쌍을 모두 살펴본다. 두 정수가 $P$ 이상인 소인수를 공유하면, 두 정수가 속한 두 집합을 하나로 합친다.

이 과정을 모두 끝냈을 때 집합은 몇 개 남는가?

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

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

제한

• $1 \le C \le 10$
• $1 \le A \le B \le 1000$
• $2 \le P \le B$

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