#include <bits/stdc++.h>

using namespace std;

const int NMAX=1000001;
int ce[NMAX];
int divs[NMAX][8];

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    //generam ciurul lui Eratostene pana la NMAX
    for(int i=2; i<=NMAX; ++i)
        if(ce[i]==0){
            ++ce[i];
            for(int k=2; k*i<=NMAX; ++k)
                ++ce[k*i];}

    //generam o matrice cu numarul maxim ce are exact j divizori
    //pentru fiecare numar i pana la NMAX
    for(int i=2; i<=NMAX; ++i)
        for(int j=1; j<=7; ++j)
            //daca i are exacr j divizori(din ciur), il retinem pe i
            if(ce[i]==j) divs[i][j]=i;
            //altfel retinem numarul anterior cu j divizori
            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;
}