NCPC 2016 D

//OM
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <sstream>
#include <algorithm>
using  namespace  std;

#define  x first
#define  y second
#define  pb push_back
#define  mp make_pair
#define  PI (acos(-1.0))
#define  mem(a,b) memset(a,b,sizeof(a))
#define  Sort(x) sort(x.begin(),x.end())
#define  FOR(i, b, e) for(int i = b; i <= (int)(e); i++)
#define  FORR(i, b, e) for(int i = b; i >=(int)(e); i--)
#define  FORI(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define  pr(x) cout<<x<<"\n"
#define  prs(x) cout<<x<<" "
#define  pr2(x,y) cout<<x<<" "<<y<<"\n"
#define  pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define  ppr(a) cout<<a.x<<" "<<a.y<<"\n"

typedef  long long ll;
typedef  pair <int, int> pii;
typedef  pair <double , double> pdd;
typedef  vector <int> vi;
typedef  vector <pii> vpii;

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction

#define  EPS 1e-9
#define  MAX 100007




ll  mul(ll  a, ll  b, ll  mod) {
    ll  ans = 0;
    while (b) {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}
ll  binByMod(ll  a, ll  to, ll  mod) {
    ll  ans = 1;
    while (to) {
        if (to & 1)
            ans = mul(ans, a, mod);
        a = mul(a, a, mod);
        to >>= 1;
    }
    return ans;
}
ll  randomll () {
    ll  ans = 0;
    for (int i = 0; i < 4; ++i)
        ans = (ans << 16) ^ rand();
    return ans;
}

bool isPrime(ll  n) {
    if (n % 2 == 0 && n != 2||n==1)
        return false;
    for (int i = 0; i < 20; ++i) {
        ll  a = (randomll () % (n - 1));
        if (a < 0)
            a += n - 1;
        a += 1;

        a = binByMod(a, (n - 1) / 2, n);
        if (a != n - 1 && a != 1)
            return false;
    }

    return true;
}
bool isquare(ll m)
{
    ll sq=(ll)(sqrt(m)+0.5);
    return sq*sq==m;
}
ll gcdll(ll a, ll b){
  if(b == 0) return a;
  return gcdll(b, a%b);
}
bool mark[10000005];
int prime[700005],K;
int  prime_gen(int n)
{
    for(int i=3;i*i<=n;i+=2)
        if(!mark[i])
            for(int j=i*i,k=i<<1;j<=n;j+=k)
            mark[j]=true;
    int k=0;
    prime[k++]=2;
    for(int i=3;i<=n;i+=2)if(!mark[i])prime[k++]=i;
    K=k;
    return k;
}
ll divisor_count(ll  n)
{
    ll divisor=1,pow;
    for(int i=0;prime[i]*prime[i]*prime[i]<=n&&i<K;i++)
    {
        if(n%prime[i]==0)
        {
            pow=0;
            while(n%prime[i]==0)
            {
                pow++;
                n/=prime[i];
            }
            divisor*=(pow+1);
        }
    }
    if(isPrime(n))divisor*=2;
    else if(isquare(n))
    {
        ll sq=(ll)(sqrt(n)+EPS);
        if(isPrime(sq))divisor*=3;
    }
    else if(n!=1)divisor*=4;
    return divisor;
}
ll divisor_count2(ll  n)
{
    ll nd=1,pow;
    vector<ll> gg;
    for(int i=0;prime[i]*prime[i]*prime[i]<=n&&i<K;i++)
    {
        if(n%prime[i]==0)
        {
            pow=0;
            while(n%prime[i]==0)
            {
                pow++;
                n/=prime[i];
            }
            gg.pb(pow);
        }
    }
    if(isPrime(n))gg.pb(1);
    else if(isquare(n))
    {
        ll sq=(ll)(sqrt(n)+EPS);
        if(isPrime(sq))gg.pb(2);
    }
    else if(n!=1)gg.pb(1);
    if(!gg.empty())nd=gg[0];
    FOR(i,1,gg.size()-1)
    {
        nd=gcdll(nd,gg[i]);
    }
    return nd;
}

int main()
{
    int T;
    ll n,a,b;
    scanf("%d",&T);
    prime_gen(1000002);
    FOR(cs,1,T)
    {
        scanf("%lld%lld",&a,&b);
        n=a;
        ll d=divisor_count2(n);
        b*=d;
        printf("Case %d: %lld\n",cs,divisor_count(b)-1);
    }
    return 0;
}