#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define LL long long

/// Graph Direction

//int dx[]={1,0,-1,0};                  int dy[]={0,1,0,-1};                // 4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};        int dy[]={0,1,1,1,0,-1,-1,-1};      // 8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};       int dy[]={1,2,2,1,-1,-2,-2,-1};     // Knight Direction
//int dx[]={-1,-1,+0,+1,+1,+0};         int dy[]={-1,+1,+2,+1,-1,-2};       // Hexagonal Direction

/*
LL power(LL n,LL p)
{
    LL ans=1;
    for(LL i=1;i<=p;i++)
    {
        ans*=n;
    }
    return ans;
}
*/

/// Bit Mask

/*
int setBit(int n,int pos)
{
    return n|(1<<pos);
}

int resetBit(int n,int pos)
{
    return n&~(1<<pos);
}

bool checkBit(int n,int pos)
{
    return n&(1<<pos);
}
*/

/// Number Theory


int p[1111111];
//int segp[1111111];
vector<int> prime;
//vector<int> factors;

LL primeFactorization(LL n)
{
    LL ans=1;
    for(int i=0;i<prime.size()&&prime[i]<=sqrt(n);i++)
    {
        if(p[n]==0)
        {
            break;
        }
        if(n%prime[i]==0)
        {
            LL cnt=0;
            while(n%prime[i]==0)
            {
                cnt++;
                //factors.push_back(prime[i]);
                n/=prime[i];
            }
            ans*=(cnt+1);
        }
    }
    if(n!=1)
    {
        //factors.push_back(n);
        ans*=2;
    }
    return ans;
}

/*LL GCD(LL a,LL b)
{
    while(b!=0)
    {
        a=a%b;
        int c=a;
        a=b;
        b=c;
    }
    return a;
}*/

/*LL LCM(LL a,LL b)
{
    return a*(b/GCD(a,b));
}

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;
}*/

/*LL modInv(LL a,LL m )
{
    LL x,y;
    ext_gcd(a,m,&x,&y);
    x%=m;
    if(x<0) x+=m;
    return x;
}*/

/*LL bigMod(LL b,LL p,LL m)
{
    LL ans=1%m;
    LL x=b%m;
    while(p)
    {
        if(p&1)
        {
            ans=(ans*x)%m;
        }
        x=(x*x)%m;
        p>>=1;
    }
    return ans;
}*/

void sieve(int n)
{
    memset(p,0,sizeof(p));
    p[0]=p[1]= 1;
    for(int i=4;i<=n;i+=2)
    {
        p[i]=1;
    }
    for(int i=3;i<=sqrt(n);i+=2)
    {
        if(p[i]==0)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                p[j]=1;
            }
        }
    }
}

/*LL segSieve(LL a,LL b)
{
    if(a==1)
    {
        a++;
    }
    memset(segp,0,sizeof(segp));
    for(int i=0;prime[i]<=sqrt(b);i++)
    {
        LL x=prime[i];
        LL j=x*x;
        if(j<a)
        {
            j=ceil(1.0*a/x)*x;
        }
        while(j<=b)
        {
            segp[(int)(j-a)]=1;
            j+=x;
        }
    }
    LL ans=0;
    for(LL i=a;i<=b;i++)
    {
        if(segp[(int)(i-a)]==0)
        {
            ans++;
        }
    }
    return ans;
}*/

/*LL eulerPhi(LL n)
{
    LL ans=n;
    LL sqrtn=sqrt(n);
    for(int i=0;i<prime.size()&&prime[i]<=sqrtn;i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
            }
            sqrtn=sqrt(n);
            ans/=prime[i];
            ans*=prime[i] - 1;
        }
    }
    if(n!=1)
    {
        ans/=n;
        ans*=n-1;
    }
    return ans;
}*/

/// Segment Tree

/*

int a[1111111];
int tree[4444444];

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=a[b];
        return;
    }
    int L=2*node;
    int R=2*node+1;
    int mid=(b+e)/2;
    init(L,b,mid);
    init(R,mid+1,e);
    tree[node]=tree[L]+tree[R];
}

void update(int node,int b,int e,int index,LL value)
{
    if(index<b||index>e)
    {
        return;
    }
    if(b==e)
    {
        tree[node]=value;
        return;
    }
    int L=2*node;
    int R=2*node+1;
    int mid=(b+e)/2;
    update(L,b,mid,index,value);
    update(R,mid+1,e,index,value);
    tree[node]=tree[L]+tree[R];
}

LL query(int node,int b,int e,int i,int j)
{
    if(j<b||i>e)
    {
        return 0;
    }
    if(b>=i&&e<=j)
    {
        return tree[node];
    }
    int L=2*node;
    int R=2*node+1;
    int mid=(b+e)/2;
    LL first=query(L,b,mid,i,j);
    LL second=query(R,mid+1,e,i,j);
    return first+second;
}
*/


int tc;
LL a,b;


int main(void)
{
    sieve(1111100);
    for(int i=2;i<1111000;i++)
    {
        if(p[i]==0)
        {
            prime.pb(i);
        }
    }
    scanf("%d",&tc);
    for(int t=1;t<=tc;t++)
    {
        scanf("%lld%lld",&a,&b);
        if(b*b>=a)
        {
            printf("Case %d: 0\n",t);
            continue;
        }
        LL pf=primeFactorization(a);
        pf/=2;
        LL ex=0;
        for(int i=1;i<b;i++)
        {
            if(a%i==0)
            {
                ex++;
            }
        }
        printf("Case %d: %lld\n",t,pf-ex);
    }
    return 0;
}