#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

using namespace std;

#define INF 1000000000

#define eps 1e-8

#define pii pair<int,int>

#define LL long long int

int m,n,k,T;

int prime[],vis[];

void getprime()

{

    int num=;

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

    {

        if(vis[i]==) prime[num++]=i;

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

        {

            if(j%i==) vis[j]=;

        }

    }

}

int main()

{

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

    //freopen("out.txt","w",stdout);

    getprime();

    scanf("%d",&T);

    for(int cas=;cas<=T;cas++)

    {

        scanf("%d%d",&m,&n);

        k=INF;

        vector<pii>zhi;

        for(int i=;prime[i]<=m;i++)

        {

            int num=;

            while(m%prime[i]==)

            {

                num++;

                m/=prime[i];

            }

            if(num)

            zhi.push_back(make_pair(prime[i],num));

        }

        for(unsigned int i=;i<zhi.size();i++)

        {

            int t=zhi[i].first,num=;

            for(int j=n;j>=;j--)

            {

                int jj=j;

                while(jj%t==)

                {

                    num++;

                    jj/=t;

                }

            }

            //cout<<'k'<<num<<endl;

            k=min(k,num/(zhi[i].second));

        }

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

        if(k)

        printf("%d\n",k);

        else

            printf("Impossible to divide\n");

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}