#include <fstream>
#include <vector>
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int ok[1000001],n,m,k;
vector <int> G[8];

void ciur()
{
    for(int i=0;i<8;i++)
        G[i].push_back(0);
    G[0].push_back(1);
    for(int i=2;i<=1000000;i++)
    {
        if(ok[i]==0)
        {
            for(int j=1;i*j<=1000000;j++)
                ok[i*j]++;
        }
        if(ok[i]<8)
            G[ok[i]].push_back(i);
    }
}

int cauta(int val)
{
    int in=0,fi=G[k].size()-1,poz=0;
    while(in<=fi)
    {
        int mid=(in+fi)/2;
        if(G[k][mid]==val)
            return G[k][mid];
        else
        if(G[k][mid]<val)
        {
            in=mid+1;
            poz=mid;
        }
        else
            fi=mid-1;
    }
    return G[k][poz];
}


int main()
{
    fin>>n;
    ciur();
    for(int i=1;i<=n;i++)
    {
        fin>>m>>k;
        fout<<cauta(m)<<"\n";
    }
    return 0;
}