#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define maxn 1100000

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f;

LL primes[maxn];

bool vis[maxn];

LL ans = ;

void init()

{

    mem(vis,);

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

        if(!vis[i])

        {

            primes[ans++] = i;

            for(LL j=(LL)i*i; j<maxn; j+=i)

                vis[j] = ;

        }

}

int main()

{

    init();

    int T, kase = ;

    scanf("%d",&T);

    LL a, b;

    while(T--)

    {

        LL res = ;

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

        if(a <= b*b)  {printf("Case %d: 0\n",++kase);continue;}

        LL x = a;

        for(LL i=; i<ans && primes[i] * primes[i] <= a; i++)

        {

            LL cnt2 = ;

            while(a % primes[i] == )

            {

                a /= primes[i];

                cnt2++;

            }

            if(cnt2 > )

            {

                res *= (cnt2 + );

//                if(primes[i] < b)

//                    ios *= (cnt2+1);

            }

        }

        if(a > )

        {

            res *= ;

//            if(a < b)

//                ios *= 2;

        }

        res /= ;

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

            if(x % i == )

                res--;

        printf("Case %d: %lld\n",++kase,res);

    }    

    return ;

}