#include <fstream>
#define NDIM 1000000

using namespace std;

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

int nr, n, d, i, v[NDIM + 2], t, nrdiv, k;

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

    f>>t;
    for(int o = 1;o <= t; ++ o)
    {
        f>>n>>k;
        while(true)
        {

            if(v[n] == k)
            {
                g<<n<<'\n';
                break;
            }
            if(n == 1)
            {
                g<<0<<'\n';
                break;
            }
            -- n;
        }
    }
    return 0;
}