LOJ 1340

#include<bits/stdc++.h>
using namespace std;


#ifdef ERFANUL007
    #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template < typename Arg1 >
    void __f(const char* name, Arg1&& arg1){
        cout << name << " = " << arg1 << std::endl;
    }
    template < typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names, ',');
        cout.write(names, comma - names) << " = " << arg1 <<" | ";
        __f(comma+1, args...);
    }
#else
    #define debug(...)
#endif

#define ll long long int

template <class T> inline T bigMod(T p,T e,T M){T ret=1; for(;e>0;e>>=1){ if(e&1) ret=(ret*p)%M; p=(p*p)%M;} return (T)ret;}

const int N = 100000;
const ll Mod = 10000019;

bool isprime[N + 2];
vector< int > prime;

void sieve(){
    memset(isprime, 1, sizeof(isprime));
    for(int i=4; i<=N; i+=2) isprime[i] = 0;
    for(int i=3; i*i<=N; i+=2){
        if(!isprime[i]) continue;
        for(int j=i*i; j<=N; j+=(i*2)){
            isprime[j] = 0;
        }
    }
    prime.push_back(2);
    for(int i=3; i<=N; i+=2){
        if(isprime[i]) prime.push_back(i);
    }
}

int primecnt(int n, int p){
    int cnt = 0;
    while(n){
        cnt += (n/p);
        n/=p;
    }
    return cnt;
}

ll getans(int n, int k){
    ll ans = 1;
    for(int i=0; i<prime.size() && prime[i]<=n; i++){
        int cnt = primecnt(n, prime[i]);
        if(cnt < k) continue;
        ll p = cnt/k;
        ans = (ans * bigMod((ll)prime[i], p, Mod)) % Mod;
        //debug(prime[i], p, ans);
    }
    if(ans == 1) return -1;
    return ans;
}

int main(){
    #ifdef ERFANUL007
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    sieve();

    int t, cs=0;
    cin >> t;

    while(t--){
        int n, k;
        cin >> n >> k;
        int ans = getans(n, k);
        cout << "Case " << ++cs << ": ";
        cout << ans << '\n';
    }

    #ifdef ERFANUL007
        fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    #endif

    return 0;
}