#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e6+2;
bool is[maxn];
int cnt =0;
ll p[maxn], prim[maxn];
int k;
void find_prim()
{
k = 0;
for(ll i = 2; i <= maxn; i++)
{
if(!p[i])
{
prim[k++] = i;
for(ll j = i+i; j <= maxn; j+=i)
{
p[j] = 1;
}
}
}
}
ll cont(ll a)
{
ll s = 1;
if(a == 0)
{
return 0;
}
ll tt = 0;
ll i = 0;
while(prim[i] < a && i < k)
{
tt = 0;
if(a%prim[i] == 0)
{
while(a%prim[i] == 0)
{
a/=prim[i];
tt++;
}
}
s *= tt+1;
i++;
}
if(a > 1)
{
s *= 1+1;//一次
}
return s;
}
int main(void)
{
//freopen("e://对拍//data.txt","r",stdin);
//freopen("e://对拍//WA.txt","w",stdout);
find_prim();
//srand(time(NUll));
int T;
ll x,y;
scanf("%d",&T);
int casee=1;
while(T--)
{
scanf("%lld%lld",&x,&y);
if(y*y>=x) {printf("Case %d: %lld\n", casee++, 0);continue;}
ll sum=cont(x);
ll ans=0;
for(ll i=1;i<y;i++)
{
if(x%i==0) ans++;
}
printf("Case %d: %lld\n", casee++, sum/2 - ans);
}
}
