#include <fstream>

using namespace std;

bool nrp[10000];

void ciur()
{
    for(int i=2; i<10000; i++)
        for(int j=i*i; j<10000; j*=i)
            nrp[j]=1;
    return;
}

int nrdiv(int x)
{
    int nr=0;
    for(int i=2; i<10000 && x>1; i++)
    {
        if(!nrp[i] && x%i==0)
        {
            nr++;
            for(; x%i==0; x/=i);
        }
    }
    return nr;
}

int fc(int n, int k)
{
    for(int i=n; i>=2; i--)
    {
        if(nrdiv(i)==k)
            return i;
    }
    return 0;
}

int main()
{
    int n, k, t=0;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>t;
    ciur();
    for(int i=0; i<t; i++)
    {
        f>>n>>k;
        g<<fc(n, k)<<"\n";
    }
    f.close();
    g.close();
    return 0;
}