#include <fstream>
#include <iostream>

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

const int MAXN=1000000;
const int MAXK=8;

int sieve[MAXN+10],dp[MAXN+10][MAXK];

void ciur()
{
    int i,j;
    for(i=2; i<MAXN; i+=2)
        sieve[i]=1;
    for(i=3; i<MAXN; i+=2)
        if(sieve[i]==0)
            for(j=i; j<MAXN; j+=i)
                sieve[j]++;
}

void solve()
{
    int i,j;
    for(i=1; i<MAXN; i++)
        for(j=0; j<MAXK; j++)
            if(sieve[i]==j)
                dp[i][j]=i;
            else
                dp[i][j]=dp[i-1][j];
}

int main()
{
    int teste,n,k;
    ciur();
    solve();
    in>>teste;
    for(int i=1; i<=teste; i++)
    {
        in>>n>>k;
        out<<dp[n][k];
    }
    return 0;
}