/** Which of the favors of your Lord will you deny ? **/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second
#define INF INT_MAX

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**
PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing
**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e6+7;
const LL LINF = 1e17;

string to_str(LL x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}


set<LL>SET;
vector<LL>v;
LL facto[nmax];
LL mod = 100000007;

// ax + by = GCD(a,b)
// r2 is GCD(a,b) and X & Y will be the co-eff of a and b respectively
LL ext_gcd ( LL A, LL B, LL &X, LL &Y )
{
    LL x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;
    return r2;
}

//when inverse of a (w.r.to mo) && mo is not prime
LL modInv_general ( LL a, LL m ) {
    LL x, y;
    ext_gcd( a, m, x, y );

    // Process x so that it is between 0 and m-1
    x %= m;
    if ( x < 0 ) x += m;
    return x;
}

void precalc1()
{
    LL lim = 1e10;

    for(LL i=2; i*i<=lim; i++)
    {
        LL val = i;

        for(LL j=1; val<=lim; j++)
        {
            val *= i;

            if(!SET.count(val))
            {
                SET.insert(val);
                v.push_back(val);
            }
        }
    }
}

void precalc2()
{
    /** SET size is around 2e5 **/

    LL lim = 1e6;

    facto[0] = 1;

    for(LL i=1; i<=lim; i++)
    {
        facto[i]=((facto[i-1]%mod)*(i%mod))%mod; //(facto[i-1]*i)%m
    }
}

LL catalan(LL n)
{
    if(n==0)
        return 0;

    LL ans1 = facto[2*n];
    LL v1 = facto[n];
    LL v2 = facto[n+1];

    LL ans2 = modInv_general(v1,mod);
    LL ans3 = modInv_general(v2,mod);

    LL ans = (ans1*ans2)%mod;
    ans = (ans*ans3)%mod;

    return ans;
}

int main()
{
    //freopen("out.txt","w",stdout);

    optimizeIO();

    precalc1();
    precalc2();

    sort(ALL(v));

    int tc;
    cin>>tc;

    for(int q=1; q<=tc; q++)
    {
        LL a,b;
        cin>>a>>b;

        LL ca = upper_bound(ALL(v),a-1)-v.begin();
        LL cb = upper_bound(ALL(v),b)-v.begin();

        LL n = cb-ca;

        LL ans = catalan(n);

        cout<<"Case "<<q<<": ";
        cout<<ans<<endl;
    }

    return 0;
}

/**
4
1 4
5 10
1 10
1 3
**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}