#include <fstream>


using namespace std;

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

const int DIM=1000000;

int m[8][DIM+1];
int v[DIM+1];
bool ciur[DIM+1];
int cnt[8];
int main()
{
    int n,t,k,i,j;
    v[2]=1;
    i=4;
    while(i<=DIM)
    {
        v[i]++;
        ciur[i]=1;
        i+=2;
    }
    for(i=3;i<DIM;i+=2)
    {
        if(ciur[i]==0)
        {
            v[i]++;
            ciur[i]=1;
            j=2*i;
            while(j<=DIM)
            {
                v[j]++;
                ciur[j]=1;
                j+=i;
            }
        }
    }
    for(i=1;i<=7;i++)
    {
        k=1;
        for(j=2;j<=DIM;j++)
        {
            if(v[j]==i)
                m[i][k++]=j;
        }
        cnt[i]=k-1;
    }

    m[0][1] = 0;

//    for(int i = 0 ; i < 8 ; i++)
//    {
//        cout << cnt[i] << endl;
//        for(int j = 0 ; j < 100 ; j++)
//            cout << m[i][j] << " " ;
//        cout << endl;
//    }

    int nr,d;
    int left,right,mid,sol;
    cin >> t;
    for(i=1;i<=t;i++)
    {
        cin >> nr >> d;

        left=1;
        right=cnt[d];
        sol = 0;
        while (left <= right)
        {
            mid = (left+right)/2;
            if (m[d][mid] == nr)
            {
                sol= nr;
                break;
            }
            else if (m[d][mid]< nr)
            {
                sol = m[d][mid];
                left = mid+1;
            }
            else
                right = mid-1;
        }
        cout << sol<< endl;
    }

    return 0;
}