#include <fstream>
#define N 1000000

using namespace std;

int n,k,T,a[N+1],b[8][N+1];

inline void Ciur()
{
    int i,j;
    for(i=2;i<=N;i+=2)
        a[i]=1;
    for(i=3;i<=N;i+=2)
        if(a[i]==0)
            for(j=i;j<=N;j+=i)
                a[j]++;
}

inline void Dinamica()
{
    int i,j;
    for(j=2;j<=N;++j)
        for(i=0;i<=7;++i)
        {
            if(a[j]!=i) b[i][j]=b[i][j-1];
            else    b[i][j]=j;
        }
}

inline void Citire()
{
    int i;
    Ciur();
    Dinamica();
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>T;
    for(i=1;i<=T;++i)
    {
        fin>>n>>k;
        fout<<b[k][n]<<"\n";
    }
    fin.close();
    fout.close();
}

int main()
{
    Citire();
    return 0;
}