#include <fstream>
using namespace std;

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

int main()
{
	int t,n,k;
	int ok,d,f,j;
	int i,nr,nr1;
	fin>>t;    //t=numarul de teste
	for(i=1;i<=t;i++)          //de cate ori se repeta algoritmul
	{
		nr1=0;
		fin>>n>>k;	
		for(j=n;j>=1;j--)
		{
			nr=0;
			if(j%2==0)
				nr++;
			for(d=3;d<=n/2;d=d+2)    // d nu poate fi 1 sau 0 si nici nu poate fi par
			{
				if(j%d==0)
				{
					f=3;
					ok=1;
					while(f*f<=d && ok==1)
					{
						if(d%f==0)
							ok=0;
						else
							d=d+2;
					}
					if(ok==1)
						nr++;
				}
			}
			if(nr==k)
			{
				fout<<j<<'\n';
				nr1++;
				break;
			}
		}
		if(nr1==0)
			fout<<"0"<<'\n';
	}
	return 0;
}