#include<iostream>
#include<fstream>
using namespace std;
int main(void)
{
	fstream f,g;
	int t,k,divprim,j,jj,i,n,ok;
	f.open("divprim.in", ios::in);
	g.open("divprim.out",ios::out);
	f>>t;
	for (i=1;i<=t;i++)
	{
		divprim=0;
		ok=1;
		f>>n;
		f>>k;	
		while (1)
			{
				n=n-1;
				for (j=2;j<=n/2;j++)
				{
					for (jj=2;jj<=j/2;jj++)
						{
							if (j%jj==0)
							   {ok=0;break;}
					    }
					if (ok==1)
						divprim=divprim++;
					else break;
				}
			if (divprim==k)
				{g<<n<<endl;break;}
			if (n==0)
				{g<<"0"; break;}
			
		    }
				
		
	}
	
f.close(); g.close();
}