#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;
		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();
	ciur();
    primi();  
	cautare();
    in.close();   
    out.close();   
    return 0;   
}