#include <fstream>

using namespace std;
#define NMAX 1000005

ifstream cin("divprim.in");
ofstream cout("divprim.out");

int ciur[1000005];
int n,k,t, a[8][379725];

int caut_bin(int x, int l )
{
    int st = 1, dr = a[l][0], poz = 0, mij;
    while(st <= dr)
    {
        mij = (st+dr)/2;
        if(a[l][mij] == x){
            return x;
        }
        else
            if(a[l][mij] < x){
                poz = mij;
                st = mij+1;
            }
            else
            dr = mij-1;
    }
    if(poz == 0) return 0;
    else
        return a[l][poz];
}

int main()
{
    int i, j, t;
    for(i=2;i<=1000000;i++)
    {
        if(ciur[i]==0)
            for(j=2;j<=1000000/i;j++)
                ciur[i*j]++;
    }
    int m;
    for(i=2;i<=1000000;i++)
    {
        if(ciur[i]==0)ciur[i]=1;
        a[ciur[i]][0]++;
        m=a[ciur[i]][0];
        a[ciur[i]][m]=i;
    }

    cin>>t;
    for(i = 1; i <= t; i++)
    {
        cin >> n >> k;
        cout<<caut_bin(n,k)<<'\n';
    }
    return 0;
}