#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");

int main()
{
    long t,n,x;
    int k,ok=1,i,nr=0;
    f>>t;
    for(i=1; i<=t; i++)
        f>>n>>k;
    for(i=1; i<=t; i++)
    {
        for(x=n; x>=1; x--)
            while(n%x==0)
            {
                if((x<2) || (x>2) && (x%2==0))
                    ok=0;
                for(int d=3; d*d<=x; d+=2)
                    if(x%d==0)
                        ok=0;
                if(ok==1)
                    nr++;
                if(nr==k)
                    g<<x<<endl;
                nr=0;
                ok=1;
            }
        if(n==1)
            g<<"0"<<endl;
    }
    return 0;
}