#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll mod=1e9+;

 int num[];

 int L,R,l,r;

 ll query(int x,int k)

 {

     if(x==) return ;

     int cnt=;

     int cp=x;

     while(cp)

     {

         num[cnt++]=cp%k;

         cp/=k;

     }

     int base=k,sum=,tot=;

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

     {

         tot+=base-sum;

         if(i%==)

         {

             sum=base;

             base*=k;

         }

     }

     int p=;

     for(int i=cnt-;i>=cnt/;i--)

     {

         p=p*k+num[i];

     }

     tot+=p-sum;

     int o=(cnt%==?cnt/:cnt/+);

     for(int i=o;i<cnt;i++)

     {

         p=p*k+num[i];

     }

     if(p<=x) tot+=;

     return 1ll*tot*(k-)+(ll)x;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     int cas=;

     while(T--)

     {

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

         ll ans=;

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

         {

             ans+=query(R,i)-query(L-,i);

         }

         printf("Case #%d: %I64d\n",++cas,ans);

     }

     return ;

 }