#include <iostream>
#include <fstream>

using namespace std;

fstream in("divprim.in",ios::in);
fstream out("divprim.out",ios::out);
const int div = 7;
const int NMAX = 1000000;
int many[div+1],m[div+1][NMAX+1];

void eras()
{
    int * prim = new int[NMAX + 1];
    for(int i=0;i<=NMAX;i++)
    prim[i] = 0;
    for(int i=2;i*i<=NMAX;i++)
    {
        if(!prim[i])
        {
            prim[i] = 1;
            for(int j = 2*i;j<=NMAX;j+=i)
                prim[j]++;
        }
    }
    for(int i=2;i<=NMAX;i++)
        m[prim[i]][++many[prim[i]]] = i;
    delete[] prim;
}

int main()
{
    int t;
    in>>t;
    eras();
    int n,k;
    for(int i=1;i<=t;i++)
    {
        in>>n>>k;
        if(k==0)
            out<<1;
        else
        {
            int x = 1;
            int y = many[k];
            int ok = 0;
            int gasit = -1;
            while(x<=y && !ok)
            {
            int mij = (x+y)/2;
            if((m[k][mij]<=n) && (m[k][mij+1]>n))
            {
                gasit = mij;
                ok = 1;
            }
            else
            {
                if(m[k][mij] > n)
                    y = mij-1;
                else
                    x = mij+1;
            }
        }
        out<<((gasit==-1) ? 0: m[k][gasit])<<'\n';
        }
    }
    return 0;
}