#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int Maxn = 100;
const int Maxd = 10;

bool nprime[Maxn];
bool mp[Maxn][Maxn];
int t;
ll a, b;
int res;

int Gcd(int x, int y) { return x? Gcd(y % x, x): y; }

void Go(ll num, int lst)
{
    if (num > b) return;
    if (a <= num) res++;
    int curl = lst % 10 * 10;
    for (int i = 0; i < Maxd; i++, curl++)
        if (nprime[curl] && mp[lst][curl])
            Go(10ll * num + i, curl);
}

int main()
{
    nprime[0] = nprime[1] = true;
    for (int i = 2; i < Maxn; i++) if (!nprime[i])
        for (int j = i + i; j < Maxn; j += i) nprime[j] = true;
    for (int i = 0; i < Maxn; i++)
        for (int j = 0; j < Maxn; j++)
            mp[i][j] = Gcd(min(i, j), max(i, j)) == 1;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%I64d %I64d", &a, &b);
        res = 0;
        for (int i = 10; i < Maxn; i++) if (nprime[i])
            Go(i, i);
        printf("Case #%d: %d\n", tc, res);
    }
    return 0;
}