/*#include<stdio.h>
#include<string.h>
#define N 1000000
int t,n,k,p[N],nrp[N],sol[8],v[N];
//p[i] == 0 if i is prime  
void ciur(int n)
{
	int i,j;  
	p[2]=0;
    for (i=2;i<=n;i++)   
    	if (p[i]==0)			
			for (j=i+i;j<=n;j+=i)   
				p[j]=1;  
}
void ciur(int n)
{  
	int i, j, nr = 1;  
	for(i=3;i<=n;i++)
		v[i]=1;
	for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1)         
		if ((p[i >> 3] & (1 << (i & 7))) == 0)   
			for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1)   
				p[j >> 3] |= (1 << (j & 7));  
	for (i = 1; 2 * i + 1 <= n; ++i)    
        if ((p[i >> 3] & (1 << (i & 7))) == 0)   
            v[2*i+1]=0;  
}  
void upvec(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(v[i]==0)
		{
			nrp[i]++;
			for(j=i+i;j<=n;j+=i)
				nrp[j]++;
		}
}
void read_solve()
{
	int i1,i,j;
	scanf("%d",&t);
	ciur(N);
	upvec(N);
	for(i1=0;i1<t;i1++)
	{
		scanf("%d%d",&n,&k);
		for(j=1;j<=n;++j)
				sol[nrp[j]]=j;
		printf("%d\n",sol[k]);
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	read_solve();
	return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
int t,n,k,p[N],nrp[N];
//p[i] == 0 if i is prime  
void ciur(int n)
{
	int i,j;  
	p[2]=0;
    for (i=2;i<=n;i++)   
    	if (p[i]==0)			
			for (j=i+i;j<=n;j+=i)   
				p[j]=1;  
}
void upvec(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(p[i]==0)
		{
			nrp[i]++;
			for(j=i+i;j<=n;j+=i)
				nrp[j]++;
		}
}
int binary_search(int val)  
{  
    int i, step;  
    for (step = 2; step <= n; step <<= 1);  
    for (i = 1; step; step >>= 1)  
        if (i + step < n && nrp[i + step] <= val)  
           i += step;  
    return i;  
}
int maxim(const void *a,const void *b)
{
	return *(int*)b-*(int*)a;
}
void read_solve()
{
	int i1,i,ok;
	scanf("%d",&t);
	ciur(N);
	upvec(N);
	for(i1=0;i1<t;i1++)
	{
		scanf("%d%d",&n,&k);
		ok=1;
		//qsort(nrp,n,sizeof(nrp[0]),maxim);
		//for(i=n-1;i>=1&&ok;i--)
		i=binary_search(k);
			if(nrp[i]==k)
			{
				printf("%d\n",i);
				//ok=0;
			}else
		//if(ok)
			printf("0\n");
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	read_solve();
	return 0;
}*/
/*#include<stdio.h>
#define N 1000000
int t,n,k,p[N],nrp[N],sol[1000000];
//p[i] == 0 if i is prime  
void ciur(int n)
{
	int i,j;  
	p[2]=0;
    for (i=2;i<=n;i++)   
    	if (p[i]==0)			
			for (j=i+i;j<=n;j+=i)   
				p[j]=1;  
}
void upvec(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(p[i]==0)
		{
			nrp[i]++;
			for(j=i+i;j<=n;j+=i)
				nrp[j]++;
		}
}
void read_solve()
{
	int i1,i,j;
	scanf("%d",&t);
	ciur(N/2);
	upvec(N/2);
	for(i1=0;i1<t;i1++)
	{
		scanf("%d%d",&n,&k);
		/*ok=1;
		for(i=n-1;i>=1&&ok;i--)
			if(nrp[i]==k)
			{
				printf("%d\n",i);
				ok=0;
			}
		if(ok)
			printf("0\n");
		for(j=1;j<=n;j++)
				sol[nrp[j]]=j;
		/*for(i=1;i<=n;i++){
			for(j=1;j<=n;j++)
				printf("%d ",sol[j]);
			printf("\n");
	//	}
		printf("%d\n",sol[k]);
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	read_solve();
	return 0;
}
*/
#include<stdio.h>
#define N 1000000
int t,n,k,p[N],nrp[N];
//p[i] == 0 if i is prime  
void ciur(int n)
{
	int i,j;  
	p[2]=0;
    for (i=2;i<=n;i++)   
    	if (p[i]==0)			
			for (j=i+i;j<=n;j+=i)   
				p[j]=1;  
}
void upvec(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(p[i]==0)
		{
			nrp[i]++;
			for(j=i+i;j<=n;j+=i)
				nrp[j]++;
		}
}
void read_solve()
{
	int i1,i,ok;
	scanf("%d",&t);
	ciur(N);
	upvec(N);
	for(i1=0;i1<t;i1++)
	{
		scanf("%d%d",&n,&k);
		ok=1;
		for(i=n-1;i>=1&&ok;i--)
			if(nrp[i]==k)
			{
				printf("%d\n",i);
				ok=0;
			}
		if(ok)
			printf("0\n");
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	read_solve();
	return 0;
}