#include <fstream>
using namespace std;

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

int main()
{
	int t,n,k,nr,v;
	int i,j,p; //pentru parcurgerea for
	int ok,d;  //pentru algoritm de numar prim
	fin>>t;
	for(i=1;i<=t;i++)    //numarul de citiri
	{
		fin>>n>>k;
		v=0;
		for(j=n;j>1;j--)     //verificam numarele mai mici ca n
		{
			nr=0;
			for(p=2;p<=j/2;p++)   //divizori a numerelor = p
			{
				if(j%p==0)        //verificam daca p este prim
				{
					ok=1;
					if(p%2==0 && p!=2)
						ok=0;
					d=3;
					while(d*d<=p && ok==1) 
					{
						if(p%d==0)
							ok=0;
						else
							p=p+2;
					}
					if(ok==1)
					{
						nr=nr+1;
					}
				}
			}
			if(nr==k)
			{
				fout<<j<<endl;
				v=v+1;
				break;
			}
		}
		if(v==0)
		fout<<"0"<<endl;
	}
	return 0;
}