10780

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <fstream>

#define ull  unsigned long long

using namespace std;


int factor[10001][1230];
int factorcount[10001][1230];
int prime[10001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(10001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*i;j<10001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<10001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

void factorize()
{
	for(int i=2;i<10001;i++)
	{
		int tmp=i;
		int j=0;
		while(tmp>1)
		{
			if(tmp%v[j]==0)
			{
				factorcount[i][j]++;
				factor[i][j]++;
				tmp/=v[j];
				j=-1;

			}
			j++;
			if(j==v.size())
			break;
		}
		for(int k=0;k<1230;k++)
		factorcount[i][k]+=factorcount[i-1][k];

	}
}

int main()
{
	primegenerator();
	factorize();
	int t,m,n;
	int kase=0;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		kase+=1;
		if(m<=1 || n<=0)
		{
			cout<<"Case "<<kase<<":\n";
			cout<<"Impossible to divide\n";
			continue;
		}
		int imposbl=0;
		double min_d=2e9;
		for(int i=0;i<1230;i++)
		{
			if(factor[m][i]>factorcount[n][i])
			{
				imposbl=1;
				break;
			}
			else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)
			{
                 min_d = factorcount[n][i]/factor[m][i];
			}
		}
		cout<<"Case "<<kase<<":\n";
		if(imposbl==1)
		{
           cout<<"Impossible to divide\n";
        }
		else
		{
            cout<<min_d<<"\n";
        }

	}


	return 0;
}