#include <fstream>

const int DIM=1000000;

using namespace std;

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

int  ma[8][DIM+1];
int  nrDiv[DIM+1];
int  cnt[8];

int  main()
{
    int nr,d;
    int left,right,mid,sol;
    int n,t,k;

    nrDiv[1]=1;
    for(int i=2; i<=DIM; i++)
    {
        k=1;
        if(nrDiv[i]==0)
        {
            for(int d=i; d<=DIM; d=d+i)
            {
                nrDiv[d]++;
            }
        }
    }
/*

    /// VARIANTA 1 50 PUNCTE
    /// BINARY SEARCH
    for(int i=1;i<=7;i++)
    {
        k=1;
        for(int j=2;j<=DIM;j++)
        {
            if(nrDiv[j]==i)
                ma[i][k++]=j; /// increment nr of divisors
        }
        cnt[i]=k-1;
    }

    cin >> t;
    for(int i=1;i<=t;i++)
    {
        cin >> nr >> d;
        left = 1;
        sol=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;
    }
*/

    for(int j=2; j<=DIM; j++)
    {
        for(int i=1; i<=7; i++)
        {
            ma[i][j]=ma[i][j-1];
        }
        ma[nrDiv[j]][j]=j;
    }

    cin >> t;
    for(int i=1;i<=t;i++)
    {
        cin >> nr >> d;
        cout << ma[d][nr]<< endl;
    }

    return 0;
}