uva - 10780

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>


using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
typedef long long int64;
typedef unsigned long long ui64;
#define READ(f) freopen(f, "r", stdin)
#define INF (1<<30)
#define pb push_back


#define Max 5000
int status[(Max/32)+1];
vector <int> primeList;
vector <pair<int,int> > primeFact;

bool Check(int N,int pos){
    return (bool)(N & (1<<pos));
}
int Set(int N,int pos){
    return N=N | (1<<pos);
}

void Rsieve() {
    int sqrtn = int(sqrt(Max));
    for(int i = 3; i <= sqrtn; i += 2) {
        if(!Check(status[i>>5], i&31) ) {
            for(int k = i*i; k<= Max; k += (i<<1)) {
                status[k>>5] = Set(status[k>>5], k&31);
            }
        }
    }

    primeList.pb(2);
    for(int i = 3; i <= Max; i+= 2) {
        if(!Check(status[i>>5], i&31) ) {
            primeList.pb(i);
        }
    }
}

void Factorize(int m) {
    primeFact.clear();
    REP(i, primeList.size()) {
        int prime = primeList[i];
        int sqtm = int( sqrt(m) );
        if(prime > sqtm) break;
        int count = 0;
        while(!(m % prime)) {
            count++;
            m /= prime;
        }
        if(count) primeFact.pb(make_pair(prime, count));
    }
    if(m > 1) primeFact.pb(make_pair(m, 1));
}

int get_power(int p, int n)
{
    int res = 0;
    for (int power = p ; power <= n ; power *= p) res += n/power;
    return res;
}


int main()
{
    //READ("input.txt");
    Rsieve();
    int t, caseNo = 0, m, n, min = INF, diff;
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        caseNo++;
        cout<<"Case "<<caseNo<<":\n";
        if(n < 1) {
            cout<<"Impossible to divide\n";
            continue;
        }
        Factorize(m);
        REP(i, primeFact.size()) {
            pair<int, int> p = primeFact[i];
            diff = get_power(p.first, n) / p.second;
            if(min < diff) min = diff;
        }
        if(diff) cout<<diff<<"\n";
        else cout<<"Impossible to divide\n";
    }
    return 0;
}