#include<fstream>   
using namespace std;   
const int N=1000001; 
ifstream in("divprim.in");   
ofstream out("divprim.out");
int mat[N][2];
int maxx,t,ok;
int prim[N];
char c[N]={0}; 
void citire()
{ 
	in>>t;
	for(int i=0;i<t;++i)
	{
		in>>mat[i][0];
		in>>mat[i][1];
		if(mat[i][0]>maxx)
			maxx=mat[i][0];
	}			
}
void ciur()
{
	c[1]=1;   
    for(int i=2; i*i<=maxx; ++i)   
        if(c[i]==0)   
            for(int j=i*i; j<=maxx; j+=i)   
                c[j]=1;   
}
void primi()
{
	prim[1]=0;
	for(int i=2;i<=maxx;++i)
		if(c[i]==0)
		for(int j=i;j<=maxx;j+=i)
			prim[j]++;
}
void cautare()
{
	//int j;
	for(int i=0;i<t;++i)
	{
		ok=1;
		while(mat[i][0]>=1&&ok!=0)
		{
			mat[i][0]--;
			if(prim[mat[i][0]]==mat[i][1])
			ok=0;
		}			
		if(ok==0) out<<mat[i][0]<<"\n";
		else out<<"0"<<"\n";
	}
}
int main()   
{   
    citire();
	ciur();
    primi();  
	cautare();
    in.close();   
    out.close();   
    return 0;   
}