#include<stdio.h>
const int N=1<<20;
int v[1<<20],a[8][N],x[N],t,n,k;
int amireprost(int x,int v[N])
{
	int i,pas=1<<19;
	for (i=0; pas!=0; pas>>=1)
		if (i+pas <=v[0] && v[i+pas]<=x)
			i+=pas;
	if (i==0) return 0;
	else return v[i];
}
void ciur()
{   
	int i,j;
	for (i=2; i<N; ++i)
		if (x[i]==0)
			for  (j=i; j<N; j+=i)
				++x[j];
}
void abc()
{
	int i;
	for (i=1;i<N;++i)
		a[ x[i] ] [ ++a[x[i]][0] ] = i;
}
int main()
{		
    int i;	
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);                              																																																																																			
	scanf("%d",&t);
	ciur();
	abc();
	/*
	for(int i=0 ; i<8 ; ++i)
	{
		for(int j=1 ; j<=a[i][0] ; ++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	*/
	for (i=1; i<=t; ++i)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",amireprost(n,a[k]));
	}
	return 0;
}