#include <iostream>
#include <fstream>

using namespace std;


ifstream fin("divprim.in");
ofstream fout("divprim.out");


int ndivp(int n)
{
    int cnt=0;
    if(n%2==0)
    {
        cnt=1;
        while(n%2==0)
            n/=2;
    }
    for(int i=3; n!=1; i++)
        if(n%i==0)
        {
            cnt++;
            while(n%i==0)
                n/=i;
        }
    return cnt;
}

void solv()
{
    int t;
    fin>>t;
    int i;
    int n,k;
    for(i=0; i<t; i++)
    {
        fin>>n>>k;
        if(n==1)
            fout<<0<<"\n";
        else
        {
            while(ndivp(n)!=k&&n!=1)
                n--;
            if(n==1)
                fout<<0<<"\n";
            else
                fout<<n<<"\n";
        }
    }
}

int main()
{
    solv();
    return 0;
}