#include <bits/stdc++.h>#define N 11100#define ll long longusing namespace std;bool isprime[N];ll prime[N], num, c[N], temp[N], c1[N], k;void doprime(ll n){    ll i,j;    num = 0;    memset(isprime, true,sizeof(isprime));    isprime[1] = 0;    for(i=2;i<=n;i++){        if(isprime[i]){            prime[num++] = i;            for(j=i*i;j<=n;j+=i) isprime[j] = false;        }    }}ll check(ll k){    ll sum = 0;    for(ll i=0; i<num; i++)        if(c[i]<k*c1[i]) return 0;    return 1;}int main(){    ll n = 5,m = 24, T, nn=1;    doprime(10100);    scanf("%lld", &T);    while(T--){        memset(c1, 0 ,sizeof(c1));        memset(c, 0 ,sizeof(c));        scanf("%lld%lld", &m, &n);        for(ll i=1;i<=n;i++) temp[i] = i;        for(ll i=0;i<num&&prime[i]<=n;i++){            ll fi = prime[i];            for(ll j=fi;j<=n;j+=prime[i])                while(temp[j]%prime[i] == 0) temp[j] /= prime[i],c[i]++;        }        for(ll i=1;i<=n;i++) if(temp[i] != 1) c[i]++;        for(ll i=0;i<num;i++)            while(m%prime[i] == 0) c1[i]++,m /= prime[i];        ll l = 0, r = 1e9, ans = 0;        while(l<=r){            ll mid = (l+r)>>1;            if(check(mid)) ans = mid, l = mid+1;            else r = mid-1;        }        cout<<"Case "<<nn++<<":\n";        if(ans == 0) cout<<"Impossible to divide\n";        else cout<<ans<<"\n";    }    return 0;}