#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

const int NMAX = 1000005;
int c[NMAX];
vector<int>v[10];

inline void ciur(int n)
{
    int lim = (int)sqrt((double)n);
    for(int i = 2 ; i <= lim ; i++)
    {
        if(c[i] == 0)
        {
            for(int j = 1 ; j <= n/i ; j++)
                c[i*j]++;
        }
    }
}

inline int raspuns(int n,int k)
{
    int st,dr,med;
    st = 0;
    int ans = 0;
    dr = v[k].size()-1;
    while(st<=dr)
    {
        med = (st+dr)/2;
        if(v[k][med] <= n)
        {
            st = med+1;
            ans = v[k][med];
        }
        else
            dr = med-1;
    }
    return ans;
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur(NMAX-5);
    for(int i = 1 ; i <= 1000000 ; i++)
        v[c[i]].push_back(i);
    int n;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",raspuns(a,b));
    }
    return 0;
}