#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=i+i; k<=NMAX; k+=i)
                ++ce[k];}
    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]<<endl;
    }
    return 0;
}