// Arup Guha
// 5/27/2013
// Solution to 2012 Rocky Mountain Regional Problem C: Dirichlet's Theorem

import java.util.*;
import java.math.*;

public class c {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		// Find our primes upto 1000000, since max value we check is 10^12.
		boolean[] sieve = new boolean[1000000];
		Arrays.fill(sieve, true);
		sieve[0] = false;
		sieve[1] = false;

		// Normal prime sieve.
		for (int i=2; i<sieve.length; i++)
			for (int j=2*i; j<sieve.length; j+=i)
				sieve[j] = false;

		long a = stdin.nextLong();
		int loop = 1;

		// Go through each case.
		while (a != 0) {

			long b = stdin.nextLong();
			long low = stdin.nextLong();
			long high = stdin.nextLong();

			// We run a modified sieve here.
			boolean[] thisSieve = new boolean[(int)(high-low+1)];
			Arrays.fill(thisSieve, true);

			// Screen out any numbers below 2 as not being prime.
			if (a*low+b < 2) thisSieve[0] = false;
			if (thisSieve.length > 1 && a*(low+1)+b < 2) thisSieve[1] = false;

			// Go through each prime < 1000000.
			for (int i=0; i<sieve.length; i++) {

				// Divide out by primes only.
				if (sieve[i]) {

					long p = i;
					
					// a has an inverse mod p.
					if (a%p > 0) {

						long[] modInv = EEA(p, a);

						long aInv = modInv[2];
						aInv = map(aInv, p);

						// All valid solutions n for an+b = 0 mod p, must have n=(a^-1)b mod p.
						long validN = (aInv*map(-b,p))%p;

						// All of this code finds the first value of n >= low that is equivalent
						// to validN mod p. There is a better way to do this, I am sure.
						validN += ((low/p)*p);
						if (validN < low)
							validN += p;
						while (validN >= low+p) validN -=p;

						// Mark all valid solutions greater than p as not prime.
						for (long j=validN; j<=high; j+=p) {

							if (a*j+b > p && (a*j+b)%p == 0)
								thisSieve[(int)(j-low)] = false;
						}
					}

					// Nothing is prime, since p divides evenly into a and b.
					else if (b%p == 0) {
						
						for (long j=low; j<=high; j++)
						
							// Double check to be sure.
							if (a*j+b > p)
								thisSieve[(int)(j-low)] = false;
						break;
					}
				}
			}

			// Count the primes!
			int cnt = 0;
			for (int i=0; i<thisSieve.length; i++)
				if (thisSieve[i])
					cnt++;

			System.out.println("Case "+loop+": "+cnt);
			loop++;
			a = stdin.nextLong();
		}
	}

	public static long map(long x, long n) {
		if (x >= 0) return x%n;
		long div = -x/n;
		x += (div+1)*n;
		return x%n;
	}

	// a, b > 0
	public static long[] EEA(long a, long b) {

		// Base case.
		if (a%b == 0) {
			long[] ans = {b, 0, 0};
			return ans;
		}

		// Usual recursive call.
		long[] ans = EEA(b, a%b);

		// Build from base case.
		if (ans[1] == 0 && ans[2] == 0) {
			long ans2[] = {ans[0], 1, -a/b};
			return ans2;
		}

		long[] ans2 = {ans[0], ans[2], ans[1]+ans[2]*(-a/b)};
		return ans2;
	}
}