#include <fstream>

using namespace std;

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

short h[1000002],a[8][1000001],nr[100001],nrd[100001];

void cb(int i,int in,int fi)
{
    if(in>fi) return;
    int m=(in+fi)/2,k=nrd[i];
    if(in==fi)
    {
        g<<nr[i]-1<<'\n';
        return;
    }
    if(a[k][m]<=nr[i] and a[k][m+1]>nr[i])
    {
        g<<a[k][m]<<'\n';
        return;
    }
    else if(a[k][m]>nr[i])
        cb(i,in,m);
    else
        cb(i,m+1,fi);
}

int main()
{
    int m=0,t,i,j;
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>nr[i]>>nrd[i];
        if(nr[i]>m) m=nr[i];
    }
    for(i=2;i<=m;i++)
    {
        if(!h[i])
        {
            a[1][0]++;
            a[1][a[1][0]]=i;
            h[i]=1;
            for(j=2*i;j<=m;j+=i)
                h[j]++;
        }
        else
        {
            a[h[i]][0]++;
            a[h[i]][a[h[i]][0]]=i;
        }
    }
    for(i=1;i<=t;i++)
    {
        if(a[nrd[i]][1]>nr[i] or !a[nrd[i]][0])
            g<<'0'<<'\n';
        else
            cb(i,1,a[nrd[i]][0]);
    }
    return 0;
}