#include<stdio.h>

#define N 1000000

int i,j,n,k,a[1000002],t,aux;

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	
	scanf("%d",&t);
	
	a[2]=1;
	
	aux=N/2;
	
	for(i=2;i<=aux;i++)
		if(a[i])
			a[i*2]=1;
	
	for(i=3;i<=N;i+=2)
		if(!a[i])
		{
			a[i]=1;
			for(j=2;j*i<=N&&j<=N;j++)
				if(!a[i*j]&&a[j])
				{
					if(j%i)
						a[i*j]=a[i]+a[j];
					else
						a[i*j]=a[j];
				}
		}
	
		for(;t;t--)
		{
			scanf("%d %d",&n,&k);
			
			if(k==0)
				printf("1\n");
			else
			{				
				for(i=n;i>=2;i--)
					if(a[i]==k)
					{
						printf("%d\n",i);
						break;
					}	
					
				if(i==1)
					printf("0\n");
			}
		}
		
		return 0;
}