수의 집합 (Small)

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

먼저 대상이 되는 정수 구간과 정수 $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$ 는 남은 집합의 개수이다.