#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);
    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,vector <int> G)
{
    int in=0,fi=G.size()-1,poz=0;
    while(in<=fi)
    {
        int mid=(in+fi)/2;
        if(G[mid]==val)
            return G[mid];
        else
        if(G[mid]<val)
        {
            in=mid+1;
            poz=mid;
        }
        else
            fi=mid-1;
    }
    return G[poz];
}


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