#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define maxn 100009

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f;

LL primes[maxn];

bool vis[maxn], bz[maxn];

int ans = ;

void init()

{

    mem(vis,);

    vis[] = ;

    for(int i=; i<maxn; i++)

        if(!vis[i])

        {

            primes[ans++] = i;

            for(LL j=(LL)i*i; j<maxn; j+=i)

                vis[j] = ;

        }

}

int main()

{

    init();

    int T;

    int kase = ;

    LL a, b;

    cin>> T;

    while(T--)

    {

        int res = ;

        mem(bz,);

        cin>> a >> b;

       // if(a <= 2) a = 2;

        int len = b - a;

        for(int i=; i<ans && primes[i] * primes[i] < b; i++)

        {

            int j = a/primes[i];

            if(j*primes[i] < a) j++;  // 我们要找到第一个大于等于a的合数，因为出的时候是向下取整  所以要判断一下

            if(j == ) j++;           // 如果j == 1 则说明 a是一个质数 但我们要找合数

            while(j * primes[i] <= b)
　　　　　　　　{

                bz[j*primes[i] - a] = ;

                j++;

            }

        }

        if(a == ) bz[] = ;     // a == 1时要特殊讨论  因为1不是一个合数，无法由比它小的质数组成，也不是一个质数，所以在标记bz数组时 没有标记 就会多算

        for(int k=; k<=len; k++)

            if(!bz[k])

                res++;

        printf("Case %d: %d\n",++kase,res);

    }

    return ;

}