#define max 1000001
int N[max];
int seq[max];
int binarySearch(int search,int n,bool w){
    int left = 0,right = n-1;
    while(left  <=  right){
        int mid = (left+right)/2;
        if(seq[mid] == search){
            return mid;
        }else if(seq[mid]>search){
            right = mid-1;
        }
        else if (seq[mid]<search){
            left = mid+1;
        }
    }
    if(w){
        return left;
    } else{
        return left-1;
    }
}
int main(int argc, char const* argv[])
{
    for(long long int i = 1;i < max;i++){
        for(long long int j = i;j < max;j = j+i){
            N[j]++;
        }
    }
    seq[0] = 1;
    seq[1] = 2;
    seq[2] = 4;
    seq[3] = 7;
    seq[4] = 9;
    seq[5] = 12;
    seq[6] = 18;
    int m = 7;
    int n = 18;
    while(n < max){
        n = n+N[n];
        seq[m++] = n;
    }

    int p;
    while(~scanf("%d",&p)){
        for(int i = 1;i <= p;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            int low = binarySearch(x,m,true);
            int high = binarySearch(y,m,false);
            //printf("low = %d,high = %d\n",seq[low],seq[high]);
            printf("Case %d: %d\n",i,high-low+1);
        }
    }



    return 0;
}