#include <cstdio>

using namespace std;

int v[1000005];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    for(int x = 2; x<= 1000005; x = x + 2){
        v[x] = 1;
    }
    for(int x = 3; x<= 1000005; x = x + 2){
        if(!v[x]){
            for(int j = x; j<= 1000005; j += x){
                v[j]++;
            }
        }
    }
    int T;
    scanf("%d",&T);
    for(int i = 1; i <= T; i++){
        int k, p, ok=0;
        scanf("%d%d", &p, &k);
        for(int c = p; c >= 2; c --){
            if(v[c]==k){
                printf("%d\n", c);
                ok = 1;
                break;
            }
        }
        if(ok == 0)
            printf("0\n");
    }
    return 0;
}