#include <iostream>
#include <fstream>
#define N 1000001
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

int a[N], sol[8][N];

void Divizori()
{
    int i, j;
    ///a[i]=cati factori primi are nr i in descompunerea lui
    for(i=2; i<=N; i++)
        if(a[i] == 0)
           for(j=i; j<=N; j+=i)
              a[j]++;
    ///sol[i][j]=j - nr  j va fi scris cu i factori primi
    for(i=2; i<=N; i++)
        sol[a[i]][i] = i;
    ///plecam cu j de la 2 deoarece coloana lui 1 va fi 0 pentru ca 1 nu se descompune in factori primi
    for(i=1; i<=7; i++)
        for(j=2; j<=N; j++)
            if(sol[i][j] == 0)
               sol[i][j]=sol[i][j-1];

}

int main()
{
    int i, k, x, n;
    Divizori();
    fin >> n;
    for(i=1; i<=n; i++)
    {
        fin >> x >> k;
        fout << sol[k][x] << "\n";
    }
    return 0;
}