#include <fstream>
#include <algorithm>
#define NDIM 1000000

using namespace std;

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

int nr, n, d, i, t, nrdiv, k, st, dr, mid;

struct pozitie
{
    int st, dr;
}poz[NDIM];

struct vect
{
    int nr, div;
}v[NDIM + 2];

bool cmp(vect a, vect b)
{
    if(a.div == b.div)
        return a.nr < b.nr;
    return a.div < b.div;
}

int main()
{
    for(i = 2;i <= NDIM; ++ i)
    {
        v[i].nr = i;
        if(v[i].div == 0)
        {
            int itin = i;
            for(int it = 1;it * itin <= NDIM;++ it)
            {
                ++ v[it * itin].div;
            }
        }
    }

    sort(v + 2, v + NDIM + 1, cmp);
    /*poz[v[2].div].st = 2;
    for(i = 2; i <= NDIM; ++ i)
    {
        if(v[i].div != v[i - 1].div)
        {
            poz[v[i - 1].div].dr = i - 1;
            poz[v[i].div].st = i;
        }

    }

    f>>t;
    for(int o = 1;o <= t; ++ o)
    {
        f>>n>>k;
        st = poz[k].st;
        dr = poz[k].dr;
        while(st <= dr)
        {
            mid = (st + dr) / 2;
            if(v[mid].nr <= n)
                st = mid + 1;
            else
                dr = mid - 1;
        }
        if(v[dr].nr > n)
            g<<0<<'\n';
        else
            g<<v[dr].nr<<'\n';
    }*/
    return 0;
}