#include<fstream>
#include<iostream>
using namespace std;
int v[1000001],nr_div[1000001],sol[1000009][9];
void ciur()
{
    long long i,j;
    for(i = 1 ; i <= 1000001 ; i++)
        v[i] = nr_div[i] = 0;
    for( i = 2 ;  i <= 1000001 ; i++)
    {
        if(v[i] == 0)
        {
            for(j = i ; j <= 1000001 ; j+=i)
            {
                v[j] = 1;
                ++nr_div[j];
            }
        }
    }
}

int main()
{
    ciur();
    int j,i;
    for(i = 1 ; i <= 1000 ; i++)
        if(sol[i][nr_div[i]] < i && nr_div[i]<9 )
            {
                for( j = i ; j <= 1000 ; j++ )
                    sol[j][nr_div[i]] = i;
            }
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    int T,n,k;
    in>>T;
    for( ; T ; --T)
    {
        in>>n>>k;
        out<<sol[n][k]<<"\n";
    }
    in.close();
    out.close();
    return 0;

}