#include <iostream>
#include <fstream>
using namespace std;



int nr(int i)
{

    int aux=i,nr=0;
    for(int j=2; j<=aux; j++)
    {
        if(aux%j==0)nr++;
        while(aux%j==0)aux/=j;
    }
    return nr;


}


int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int t,n,k;
    fin>>t;
    while(t)
    {
        fin>>n>>k;
        while(nr(n)!=k&&n!=0)
        {
            n--;
        }

        if(n==0)fout<<0<<endl;
        else fout<<n<<endl;


        t--;
    }

    return 0;
}