#include<stdio.h>
int t,a[1000001];
void ciur(){
	int i,j;
	for(i=2; i<=1000000; ++i)
		if(!a[i])
			for(j=2*i; j<=1000000; j+=i)
                ++a[j];}
void solve(){
    int i,j,n,k;
    scanf("%d",&t);
    for(i=1; i<=t; ++i){
        scanf("%d%d",&n,&k);
		for(j=n; j>0; --j)
            if(a[j]==k){
                printf("%d\n",j);
                break;}
        if(j==0)
            printf("0\n");}}            
int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur();
    solve();
    return 0;}