#include <fstream>
#include <iostream>

using namespace std;

int main()
{
    int t,n,k,i,nr,j,nu,y;
    cin>>t;
    for(i=0; i<t; i++)
    {
        nr=1;
        cin>>n>>k;
        for(j=2; k>0; j++)
        {
            nu=0;
            if(j%2==0&&j!=2)
                nu=1;
            else
            {
                for(y=3; y*y<=j; y+=2)
                {
                    if(j%y==0)
                    {
                        nu=1;
                        break;
                    }
                }
            }
            if(nu==0)
            {
                nr=nr*j;
                k--;
            }
        }
        if(nr>n)
            cout<<"0\n";
        else
        {
            while(n>0)
            {
                if(n%nr==0)
                {
                    cout<<n<<"\n";
                    break;
                }
                n--;
            }
        }
    }
    return 0;
}