#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 yo[6][N]={0};
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()
{
	int j;
	prim[1]=0;
	for(int i=2;i<=maxx;++i)
		if(c[i]==0)
			for(j=i;j<=maxx;j+=i)
				prim[j]++;
}
void clasificare()
{
	int i;
	for(i=1;i<=maxx;++i)
		yo[prim[i]][i]=1;
	
}
void cautare()
{
	for(int i=0;i<t;++i)
	{
		ok=1;
		while(mat[i][0]>=1&&ok!=0)
			if(yo[mat[i][1]][mat[i][0]]!=0)
				ok=0;
			else
				mat[i][0]--;
		if(ok==0)
			out<<mat[i][0]<<"\n";
		else 
			out<<"0"<<"\n";
	}
}
int main()   
{   
    citire();
	ciur();
    primi(); 
	clasificare();	
	cautare();
    in.close();   
    out.close();   
    return 0;   
}