segmented sieve

// segmented sieve
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1e9 + 7;

const int N = 1e7 + 10;

bitset<N> arr;int prime[1000050],p;

void sieve(int n) {
    for(int i = 0; i <= n; i++) arr[i] = 0;
    double z = sqrt(n);
    arr[0] = arr[1] = 1;
    for(int i = 4; i <= n; i += 2) arr[i] = 1;
    for(int i = 3; i <= z; i += 2) {
        if(arr[i] == 0)
        for(ll j = i*i; j <= n; j += i + i) {
            arr[j] = 1;
        }
    }
    prime[p++] = 2;
    for(int i = 3; i <= n; i += 2) if(!arr[i]) prime[p++] = i;
}

int main() {

    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    sieve(1e6);
    int t,ajinka = 1;
    scanf("%d",&t);
    while(t--) {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        vector<int> mark(100005);
        ll mx = 0;
        for(int i = 0; i < p && prime[i] <= r; i++) {
            ll low = l / prime[i] * prime[i];
            if(low < l) low += prime[i];
            if(low == prime[i]) low += prime[i];
            for(ll j = low; j <= r; j += prime[i]) {
                mark[j - l] = 1;
            }
        }
        int ans = 0;
        for(ll i = l; i <= r; i++) if(!mark[i-l] && i > 1) ans ++;
        printf("Case %d: %d\n",ajinka++,ans);
    }
    return 0;
}