#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define ll long long

using namespace std;

int const MAX = 1e6 + ;

int p[MAX];

bool u[MAX];

int num, cnt;

ll a, b, tmp;

void get_prime()

{

    memset(u, false, sizeof(u));

    for(int i = ; i <= sqrt(MAX); i++)

        if(!u[i])

            for(int j = i * i; j <= MAX; j += i)

                u[j] = true;

    for(int i = ; i <= MAX; i++)

        if(!u[i])

            p[cnt ++] = i;

}

void cal()

{

    for(int i = ; i < cnt && p[i] <= sqrt(tmp); i++)

    {

        int cc = ;

        while(tmp % p[i] == )

        {

            cc ++;

            tmp /= p[i];

        }

        num *= (cc + );

    }

    if(tmp > ) //如果tmp不能被整分，说明还有一个素数是它的约数，此时cc=1

        num *= ;

}

int main()

{

    int T;

    scanf("%d", &T);

    cnt = ;

    get_prime();

    for(int ca = ; ca <= T; ca++)

    {

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

        if(a < b * b)

            printf("Case %d: 0\n", ca);

        else

        {

            num = ;

            tmp = a;

            cal();

            num /= ;

            for(int i = ; i < b; i++)

                if(a % i == )

                    num --;

            printf("Case %d: %d\n", ca, num);

        }

    }

}