#include<bits/stdc++.h>
#define ll long long
#define MAX 1000005

using namespace std;

bool  prime[MAX];

ll PRIME[MAX];

int ind=0;

void seive()
{
    for(int i=3; i<=MAX; i+=2)
        prime[i]=true;

    prime[2]=true;

    int k=sqrt(MAX);

    for(int i=3; i<=k; i+=2)
    {
        if(prime[i]==true)

            for(int j=i*i; j<=MAX; j+=(2*i))
                prime[j]=false;
    }

    PRIME[ind++] = 2;

    for(int i=3; i<=MAX; i+=2)
    {
        if(prime[i])
            PRIME[ind++] = i;
    }

}


int main()
{

    ll n,cnt,test,b,temp;

    seive();

    scanf("%lld",&test);

    for(int t = 1; t<=test; t++)
    {
        cnt=1;

        ll div;

        scanf("%lld %lld",&n,&b);

        if(b*b>=n)
        {
            printf("Case %d: 0\n",t);
        }

        else
        {

            temp = n;

            for(ll i=0; PRIME[i]<=sqrt(n)&&i<ind; i++)
            {
                if((n/PRIME[i])*PRIME[i]==n)
                {
                    div=0;
                    while((n/PRIME[i])*PRIME[i]==n)
                    {
                        div++;
                        n/=PRIME[i];
                    }

                    cnt*=(div+1);
                }
            }

            if(n>1)
                cnt*=2;

            cnt/=2;

            div = 0;

            n=temp;

            for(int i=1; i<b; i++)
            {
                if(n%i==0)
                    div++;
            }

            printf("Case %d: %lld\n",t,cnt-div);

        }

    }

    return 0;
}