#include <fstream>

const int DIM=1000000;

using namespace std;

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

int  ma[10][DIM];
int  nrDiv[DIM+1];
bool ciur[DIM+1];
int  cnt[8];

int  main()
{
    int n,t,k,i,j;
    nrDiv[2]=1;
    i=4;
    while(i<=DIM)
    {
        nrDiv[i]++;
        ciur[i]=1;
        i+=2;
    }
    for(i=3;i<DIM;i+=2)
    {
        if(ciur[i]==0) /// nr prim
        {
            nrDiv[i]++;
            j=2*i;
            while(j<=DIM)
            {
                nrDiv[j]++;
                ciur[j]=1;
                j+=i;
            }
        }
    }

    //for(i=1;i<100;i++)
    //{
    //    cout << " i " << i << " ciur " << ciur[i] << " nrDiv " << nrDiv[i] << endl;
    //}
    //return 0;
    for(i=1;i<=7;i++)
    {
        k=1;
        for(j=2;j<=DIM;j++)
        {
            if(nrDiv[j]==i)
                ma[i][k++]=j; /// increment nr of divisors
        }
        cnt[i]=k-1;
    }
/*
    for ( int i =  1 ; i <=7 ; i++)
    {
        for(int j = 2; j <= DIM ; j++)
            cout << ma[i][j] << " ";
        cout << endl;
    }
    cout << " pos :" << endl;
    for ( int i =  1 ; i <=7 ; i++)
    {
        cout << cnt[i] << " ";
    }
  */
    int nr,d;
    int left,right,mid,sol;
    cin >> t;
    for(i=1;i<=t;i++)
    {
        cin >> nr >> d;
        left = 0;
        right = cnt[d];
        while(left<= right)
        {
            mid = (left + right)/2;
            if(ma[d][mid] < nr )
            {
                sol = ma[d][mid];
                left = mid + 1;
            }
            else if (ma[d][mid] > nr )
            {
                right= mid -1;
            }
            else
            {
                sol =  ma[d][mid];
                break;
            }
        }
        cout << sol<< endl;
    }

    return 0;
}