1 //Accepted    0 KB    12 ms
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 const int MAXN = 100005;
 6 const int inf = 100000000;
 7 int pri[MAXN];
 8 int cnt;
 9 void prime()
10 {
11     cnt=0;
12     for (int i=2;i<MAXN;i++)
13     {
14         if (!pri[i])
15         {
16             pri[cnt++]=i;
17             if ((long long )i*i<(long long )MAXN)
18             for (int j=i*i;j<MAXN;j+=i)
19             pri[j]=1;
20         }
21     }
22 }
23 int p[100],pNum[100];
24 int num;
25 void getp(int n)
26 {
27     num=0;
28     memset(pNum,0,sizeof(pNum));
29     for (int i=0;i<cnt && pri[i]*pri[i]<=n;i++)
30     {
31         if (n%pri[i]==0)
32         {
33             while (n%pri[i]==0)
34             {
35                 n/=pri[i];
36                 pNum[num]++;
37             }
38             p[num++]=pri[i];
39         }
40     }
41     if (n!=1)
42     {
43         pNum[num]=1;
44         p[num++]=n;
45     }
46 }
47 int getn(int n,int m)
48 {
49     int ans=0;
50     while (n>0)
51     {
52         ans+=n/m;
53         n/=m;
54     }
55     return ans;
56 }
57 int min(int a,int b)
58 {
59     return a>b?b:a;
60 }
61 int slove(int n,int m)
62 {
63     getp(m);
64     int ans=inf;
65     for (int i=0;i<num;i++)
66     {
67         ans=min(ans,getn(n,p[i])/pNum[i]);
68     }
69     return ans;
70 }
71 int n,m;
72 int main()
73 {
74     prime();
75     int T;
76     scanf("%d",&T);
77     for (int t=1;t<=T;t++)
78     {
79         scanf("%d%d",&m,&n);
80         int ans=slove(n,m);
81         printf("Case %d:\n",t);
82         if (ans==0)
83         printf("Impossible to divide\n");
84         else
85         printf("%d\n",ans);
86     }
87     return 0;
88 }