#include <iostream>
#include <fstream>


#define max 1000000

using namespace std;


int v[max+1],t,k;
long b;
long mat[9][1000001],ind[10];

long cauta(int k,long b)
{
    long li=0;
    long ls = ind[k]-1,m;
    do
    {
        m = (ls+li)/2;
        if(b==mat[k][m]) return b;
        else
        {
            if(b>mat[k][m])
            {
                if(b<mat[k][m+1]) return mat[k][m];
                li = m+1;
            }
            if(b<mat[k][m])
            {
                if(b>mat[k][m-1]) return mat[k][m-1];
                ls =m-1;
            }
        }


    }while(li<ls);
    return 0;

}


int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");

    for(long i = 2;i<=max/2;i++)
    {
        mat[v[i]][ind[v[i]]++]=i;
        if(v[i] == 0 && i<=max/2)
            for(long j = i;j<=max;j+=i)
                v[j]++;

    }

    f>>t;
    for(int i = 0;i<t;i++)
    {
        f>>b>>k;
        g<<cauta(k,b)<<'\n';

    }

    f.close();
    g.close();

    return 0;
}