#include<stdio.h>
#define N 1000001

int n,t,kdiv[N],k,i,j,sol[N][9];

void ciur()
{        for(i=2;i*i<=N;i++)
		if(!kdiv[i])
		{       j=2;
			while(i*j<=N)
                        {       kdiv[i*j]++;
				j++;
			}
			kdiv[i]=1;
                }
}
int main()
{       freopen("divprim.in","r",stdin);
        freopen("divprim.out","w",stdout);
	ciur();
	for(i=2;i<N;i++)
	{       for(j=0;j<=7;j++)
			sol[i][j]=sol[i-1][j];
		sol[i][kdiv[i]]=i;
	}
	scanf("%d",&t);
	for(j=1;j<=t;j++)
	{       scanf("%d%d",&n,&k);
		printf("%d\n",sol[n][k]);
	}
        return 0;
}