#include <iostream>
#include <stdio.h>
using namespace std;
const int NMAX=1000000;
const int KMAX=8;
int ciur[NMAX+5];
int dp[NMAX][KMAX];
int main()
{
    int i,j,n,k,t;
    FILE *fin, *fout;
    fin=fopen("divprim.in", "r");
    fout=fopen("divprim.out", "w");
    ///construirea ciurului:

    for(i=2; i<=NMAX; i=i+2) ciur[i]=1;
    for(i=3; i<=NMAX; i=i+2){
        if(!ciur[i]){
            for(j=i; j<=NMAX; j=j+i)
                ciur[j]++;
        }
    }

    for(i=1; i<=NMAX; i++)
        for(j=0; j<KMAX; j++)
            if(ciur[i]==j)
                dp[i][j]=i;
            else dp[i][j]=dp[i-1][j];

    ///determinarea raspunsului
    fscanf(fin, "%d", &t);
    while(t--){
        fscanf(fin, "%d%d", &n, &k);
        fprintf(fout, "%d\n", dp[n][k]);
    }
    return 0;
}