#include <bits/stdc++.h>
using namespace std;

int ciur[1001000],a[10][1000010],l[10],t,x,k,p,st,m,dr;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur[0]=ciur[1]=1;
    for(int i=2;i<=1000000;i++)
        if(ciur[i]==0)
         for(int j=1;i*j<=1000000;j++)
            ciur[i*j]++;
    for(int i=1;i<=100000;i++)
        a[ciur[i]][++l[ciur[i]]]=i;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>x>>k;
        if(k==0) cout<<1<<'\n';
        else
        {
        st=0;
        dr=l[k];
        while(dr-st>1)
        {
            m=st+(dr-st)/2;
            if(a[k][m]>=x) dr=m;
            else st=m;
        }
        cout<<a[k][st]<<'\n';
        }
    }
    return 0;
}