/*
    Pentru fiecare n si k dat, trebui sa aflam o valoare V ai :
    - V<=n;
    - V are k divizori primi
    - V e cel mai mare posibil
*/

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k, nr[1000001], rez[1000001][10];

int main()
{
    ///determinam pentru fiecare nr cati divizori primi are cu ajutorul unui algoritm de tipul Ciurului lui Eratostene
    for(int i=2; i<=1000000; i++)
        if( nr[i]==0)
         for(int j=i; j<=1000000; j+=i)
                 nr[j]++;

    ///construim matricea rez cu semniicatia ca rez[i][j]=cel mai mare numar, mai mic sau egal decat i si are j divizori primi
    for(int i=1; i<=1000000; i++)
        for(int j=1; j<=7; j++)
            if( nr[i]==j && i>rez[i-1][j]) ///daca i are fix j divizori primi si i>cel mai mare numar, mai mic sau egal decat i-1 si are j div
                rez[i][j]=i; ///rez[i][j]=i;
            else
                rez[i][j]=rez[i-1][j];

    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        fout<<rez[n][k]<<"\n";
    }

    return 0;
}


/*
    Exemplul 1:
    -----------
        i=7;
        j=2;

        am afalt deja ca pentru i=6 si j=2 -> rez=6

        i    j   rez
        7    2    ?
        6    2    6

         Stim ca in intervalul [1, 6] cel mai mare numar <= 6 cu exact 2 divizori e 6
         Ne punem intrebarea: in intervalul [1, 7] cel mai mare numar <=7 cu exat 2 divizori e ... ?

         Observam ca al doilea interval are doar un numar in plus fata de primul, are in plus nr 7
            => exista doua varinte
            1) Nr cautat este 7
            2) Nr cautat este 6
            Cum 7 are doar un divizor => varianta 2) este corecta => pt. i=7 si j=2 -> rez=6

    Exemplul 2:
    -----------
        i=10;
        j=2;

        am afalt deja ca pentru i=9 si j=2 -> rez=6

        i    j   rez
        10   2    ?
         9   2    6

         Stim ca in intervalul [1, 9] cel mai mare numar <= 9 cu exact 2 divizori e 6
         Ne punem intrebarea: in intervalul [1, 10] cel mai mare numar <=10 cu exat 2 divizori e ... ?

         Observam ca al doilea interval are doar un numar in plus fata de primul, are in plus nr 10
            => exista doua varinte
            1) Nr cautat este 10
            2) Nr cautat este 6
            Cum 10 are fix doi divizori si noi cautam cel mai mare nr care satidface cerinta => pt. i=10 si j=9 -> rez=10

*/