#include <fstream>

using namespace std;

int main()
{
	ifstream cin("divprim.in");
	ofstream cout("divprim.out");

    int t,n,k,cnt=0,d=2,cj,nr=0;
    cin>>t;

    for(int i=0;i<t;i++)
    {
		cin>>n>>k;
		nr=0;
		for(int j=n;j>1;j--)
		{
			cnt=0;
			d=2;
			cj=j;
			while(cj>1)
			{
				if(cj%d==0)
					cnt++;
				while(cj%d==0)
				{
					cj/=d;
				}
				d++;
			}
			if(cnt==k)
			{
				nr=j;
				break;
			}

		}
		cout<<nr<<'\n';
    }

    return 0;
}