#include <iostream>
#include<fstream>
#define Max 1000005
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int ciur[Max],nrp,a[8][Max];
void construire_ciur()
{
    int i,j;
    for(i=2;i<=Max-5;i++)
        if(ciur[i]==0)
        {
            ciur[i]=1;
            for(j=2*i;j<=Max-5;j+=i)
                ciur[j]++;
        }
}
void matrice()
{
    int i;
    for(i=1;i<=Max-5;i++)
        {
            a[ciur[i]][0]++;
            a[ciur[i]][a[ciur[i]][0]]=i;
        }
}
int bs(int n,int k)
{
    int i,j,mid;
    i=1; j=a[k][0];
    while(i<=j)
    {
        mid=(i+j)/2;
        if(a[k][mid]==n)
            return n;
        if(a[k][mid]>n)
            j=mid-1;
        else
            i=mid+1;
    }
    if(a[k][j]<n)return a[k][j];
    return 0;
}
void solve()
{
    int test,t,i,n,k;
    f>>t; construire_ciur(); matrice();
    for(test=1;test<=t;test++)
    {
        f>>n>>k;
        if(k==0)g<<1; else
        g<<bs(n,k)<<'\n';
    }
}
int main()
{
    solve();
    return 0;
}