#include<bitset>

 #include<map>

 #include<vector>

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<set>

 #define inf 0x3f3f3f3f

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

 using namespace std;

 typedef long long ll;

 //输入挂

 inline ll in()

 {

     ll res=;char c;

     while((c=getchar())<'' || c>'');

     while(c>='' && c<='')res=res*+c-'',c=getchar();

     return res;

 }

 const int N=;

 ll prime[];

 int p;

 bitset<N> vis;

 void init()

 {

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

     {

         if(!vis[i])

         {

             prime[p++]=i;

             for(int j=i+i;j<N;j+=i)

             {

                 vis[j]=;

             }

         }

     }

 }

 int main()

 {

     int T = in();

     int ii = ;

     init();

     while(T--)

     {

         ll area = in(),min_side = in();

         if(min_side >= sqrt(area)){

             printf("Case %d: %d\n",ii++,);

             continue;

         }

         ll tmp = area;

         int ans = ;

         for(int i = ;i < p && prime[i]*prime[i] <= area;i++)

         {

             int cnt = ;

             while(area%prime[i] == )

             {

                 area /= prime[i];

                 cnt++;

             }

             ans *= (cnt+);

         }

         if(area != ) ans <<= ;

         ans >>= ;  //因数的个数除以二就是组数，同时排除了平方根

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

             if(tmp%i == ) ans--; //min_side此时是小于sqrt（area）的

         printf("Case %d: %d\n",ii++,ans);

     }

     return ;

 }