#include <fstream>

using namespace std;
short ciur[1000005];
int mat[10][1000005];
int poz[10];
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    ciur[0]=ciur[1]=0;
    for(int i=2;2*i<=1000005;i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i+i;j<=1000005;j+=i)
            {
                ciur[j]++;
            }
        }
    }
    for(int i=0;i<=7;i++)
    {
        poz[i]=1;
    }
    mat[0][1]=1;
    poz[0]=2;
    for(int i=2;i<=1000000;i++)
    {
        if(ciur[i]==0)
        {
            ciur[i]++;
        }
        mat[ciur[i]][poz[ciur[i]]]=i;
        poz[ciur[i]]++;
    }
    int t,a,b,st,dr,val=0,mij;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>a>>b;
        st=1;dr=poz[b]-1;val=0;
        while(dr>=st)
        {
            mij=(st+dr)/2;
            if(mat[b][mij]<=a)
            {
                val=mat[b][mij];
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        cout<<val<<'\n';
    }
    return 0;
}