Dirichlet's Theorem on Arithmetic Progressions

Dirichlet's theorem on arithmetic progressions states that for two coprime positive integers $a$ and $b$, the arithmetic progression $t(n) = a \cdot n + b$ ($n \ge 0$) contains infinitely many primes.

A prime is a positive integer greater than $1$ whose only divisors are $1$ and itself.

For example, when $a = 4$ and $b = 3$, the progression is:

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

Even just the beginning of this progression clearly contains many primes.

Given a positive integer $a > 0$, an integer $b \ge 0$, and $U \ge L \ge 0$, write a program that counts how many of the terms $t(n) = a \cdot n + b$ for $L \le n \le U$ are prime.

The input consists of several test cases. Each test case is a single line containing four integers $a$, $b$, $L$, and $U$. It is guaranteed that $a \cdot U + b \le 10^{12}$ and $U - L \le 10^{6}$. The last line contains a single $0$, which marks the end of the input.

For each test case, print one line in the format Case x: c, where $x$ is the test case number starting from $1$ and $c$ is the number of terms $t(n)$ that are prime for $L \le n \le U$.