#include <bits/stdc++.h>
const int NMAX=1000001;
using namespace std;
int ce[NMAX];
int divs[NMAX][8];
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    for(int i=2; i<=NMAX; ++i)
        if(ce[i]==0){
            ++ce[i];
            for(int k=2; k*i<=NMAX; ++k)
                ++ce[k*i];}
    for(int i=2; i<=NMAX; ++i)
        for(int j=1; j<=7; ++j)
            if(ce[i]==j) divs[i][j]=i;
            else divs[i][j]=divs[i-1][j];
    int t=0, n=0, k=0;
    f>>t;
    for(int i=0; i<t; ++i)
    {
        f>>n>>k;
        g<<divs[n][k]<<"\n";
    }
    return 0;
}