#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

int ndiv[1000001],a[1000001][8];
int n, m, t, i, st, dr, k, j;

int main()
{
    ndiv[1]=0;
    for(i=2; i<=1000000; ++i)
    {
        if(!ndiv[i])
        {
            for(j=1; i*j<=1000000; ++j) ndiv[i*j]++;
        }
    }
    /*for(i=1; i<=10; ++i) fout<<i<<" ";
    fout<<"\n";
    for(i=1; i<=10; ++i) fout<<ndiv[i]<<" ";*/
    for(i=1; i<=1000000; ++i)
    {
        for(j=0; j<=7; ++j)
        {
            if(ndiv[i]==j) a[i][j]=i;
            else a[i][j]=a[i-1][j];
        }
    }
    fin>>t;
    for(i=1; i<=t; ++i)
    {
        fin>>n>>k;
        fout<<a[n][k]<<"\n";
    }
    return 0;
}