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