등차수열에 관한 디리클레의 정리

등차수열에 관한 디리클레의 정리는 다음과 같다. 서로소인 두 양의 정수 $a$와 $b$에 대하여, 등차수열 $t(n) = a \cdot n + b$ ($n \ge 0$)에는 무한히 많은 소수가 들어 있다.

소수란 $1$보다 큰 양의 정수 중에서 약수가 $1$과 자기 자신뿐인 수를 말한다.

예를 들어 $a = 4$, $b = 3$이면 등차수열은 다음과 같다.

$3,\ 7,\ 11,\ 15,\ 19,\ 23,\ 27,\ 31,\ 35,\ \dots$

수열의 앞부분만 보아도 소수가 많이 들어 있음을 알 수 있다.

양의 정수 $a > 0$, 정수 $b \ge 0$, 그리고 $U \ge L \ge 0$이 주어질 때, $L \le n \le U$ 범위에서 $t(n) = a \cdot n + b$가 소수인 항이 몇 개인지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 네 정수 $a$, $b$, $L$, $U$가 주어진다. $a \cdot U + b \le 10^{12}$이고 $U - L \le 10^{6}$이다. 입력의 마지막 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 뜻한다.

각 테스트 케이스마다 Case x: c 형식으로 한 줄씩 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $c$는 $L \le n \le U$ 범위에서 $t(n)$이 소수인 항의 개수이다.