#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
    ll n,m,k,i,j,power,num,t,cas,sum;
    cin>>t;
    for(cas=1;cas<=t;cas++)
    {
        cin>>n>>m;
        ll vag=2,res=1e9;
        while(n>1)
        {
          power=0;
          while(n%vag==0)
          {
              n/=vag;
              power++;
          }
          if(power)
          {
              num=m,sum=0;
              while(num)
              {
                  num/=vag;
                  sum+=num;
              }
              res=min(res,sum/power);
          }
          vag++;
        }
        cout<<"Case "<<cas<<":"<<endl;
        if(res)
        cout<<res<<endl;
        else
            cout<<"Impossible to divide"<<endl;
    }
    return 0;
}