/*

HDU 6156 - Palindrome Function [ 数位DP ]  |  2017 中国大学生程序设计竞赛 - 网络选拔赛

2-36进制下回文串个数

*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long

int t, L, R, l, r, base;

int dig[40], tmp[40];

LL dp[40][40][40][2];

LL DFS(int pos, int start, bool state, bool limit)

{

    if (pos < 0) return state;

    if (!limit && dp[base][pos][start][state] != -1) return dp[base][pos][start][state];

    int end = (limit ? dig[pos] : base-1);

    LL res = 0;

    for (int i = 0; i <= end; i++)

    {

        tmp[pos] = i;

        if (pos == start && i == 0)

        {

            res += DFS(pos-1, start-1, state, limit && (i == end));

        }

        else if (state && pos < (start+1)/2)

        {

            res += DFS(pos-1, start, tmp[start-pos] == i, limit && (i == end));

        }

        else

        {

            res += DFS(pos-1, start, state, limit&&(i == end));

        }

    }

    if (!limit) dp[base][pos][start][state] = res;

    return res;

}

LL Cal(LL x)

{

    int len = 0;

    while (x)

    {

        dig[len++] = x % base;

        x /= base;

    }

    return DFS(len-1, len-1, 1, 1);

}

LL solve()

{

    LL num = (Cal(R) - Cal(L-1));

    return num*base + (R-L+1-num);

}

int main()

{

    memset(dp, -1, sizeof(dp));

    scanf("%d", &t);

    for (int tt = 1; tt <= t; tt++)

    {

        scanf("%d%d%d%d", &L, &R, &l, &r);

        LL ans = 0;

        for (int i = l; i <= r; i++)

        {

            base = i;

            ans += solve();

        }

        printf("Case #%d: %lld\n", tt, ans);

    }

}