Dev Skill Mr. And Mrs. A

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define high 1000003
#define mxhigh 1000000000003

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef set<LL>sll;

LL sze=0;

vll v;

void fun()
{
    LL i, j;
    sll st;
    sll ::iterator it;

    for(i=2; i<high; i++)
    {
        LL p=1;

        for(j=2; j<40; j++)
        {
            p = powl(i , j);

            if(p > mxhigh) break;

            if(p <= mxhigh)
            {
                st.insert(p);
            }
        }
    }

    for(it=st.begin() ; it!=st.end() ; ++it)
    {
        v.push_back(*it);
    }

    //for(i=0; i<100; i++) cout << v[i] << " ";
    //cout << v.size();
    //cout << v[v.size()-1];
    sze = v.size();
}

LL khoj(LL lo, LL hi, LL itm)
{
    LL mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(v[mid] == itm) return mid;
        else if(v[mid] > itm) hi = mid - 1;
        else if(v[mid] < itm) lo = mid + 1;
    }

    return lo;
}

int main()
{
    fun();
    int t , tc=0;
    LL x , y , lr, upr;

    sf("%d", &t);

    while(t--)
    {
        sf("%lld %lld", &x , &y);

        lr = khoj(0, sze-1, x);

        upr = khoj(0, sze-1, y);

        if(v[upr] != y) upr--;

        pf("Case %d: %lld\n" , ++tc , upr - lr + 1);
    }

    return 0;
}