#include<fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int ciur[1000001], m[8][1000001], n[100001], k[100001];
int main()
{
    int t, i, maxim, d, st, dr, pos, nr;
    maxim=0;
    cin>>t;
    for(i=1; i<=t; i++)
    {
        cin>>n[i]>>k[i];
        if(n[i] > maxim)
            maxim=n[i];
    }
    for(d=2; d <= maxim; d++)
        if(ciur[d] == 0)
            for(i=d; i<=maxim; i+=d)
                ciur[i]++;
    for(i=1; i<=maxim; i++)
    {
        m[ciur[i]][m[ciur[i]][0]+1]=i;
        m[ciur[i]][0]++;
    }
    for(i=1; i<=t; i++)
    {
        nr=0;
        st=1;
        dr=m[k[i]][0];
        while(st <= dr)
        {
            pos=(st+dr)/2;
            if(m[k[i]][pos] > n[i])
                dr=pos-1;
            else
            {
                nr=m[k[i]][pos];
                st=pos+1;
            }
        }
        cout<<nr<<'\n';
    }
    return 0;
}