#include <fstream>
#include <cmath>
using namespace std;
int main()
{
    ifstream in("gfact.in");
    ofstream out("gfact.out");
    int t;in>>t;
    while(t){
    int p,q,ok=0;
    in>>p>>q;
    long long a=pow(p,q),b=0;
    while(ok==0)
    {
        b++;
        long long y=1,fact=1;
        while(y<=b)
        {
            fact=fact*y;
            y++;
        }
        if(fact%a==0)ok=1;
    }
    out<<b<<"\n";
    t--;
    }
    in.close();
    out.close();
    return 0;
}