#include <fstream>
using namespace std;
ifstream cin ("divprim.in");
ofstream cout ("divprim.out");
const int NMAX=400005,DIM=1000005;
int a[8][NMAX],c[DIM],aux[8];
void ciur()
{
    c[0]=c[1]=0;
    for(int i=2; i<=DIM; i+=2)
        c[i]++;
    for(int i=3; i<=DIM; i+=2)
        if(!c[i])
            for(int j=i; j<=DIM; j+=i)
                c[j]++;
}
void bucket()
{
    for(int i=0; i<=DIM; i++)
        a[c[i]][++aux[c[i]]]=i;
}
int cb(int x, int y)
{
    if(x<a[y][1])
        return 0;
    int st=1, dr=aux[y], res=1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[y][mij]<=x)
        {
            res=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return a[y][res];
}
int main()
{
    int m;
    cin>>m;
    ciur();
    bucket();
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<cb(x,y)<<'\n';
    }
    return 0;
}