#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define maxi 1000000
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int nrdiv[maxi+5],a[8][maxi+5],t,n,k;
bool prim[maxi+5];
void CIURULETZ()
{
    memset(prim,true,sizeof(prim));
    prim[0]=false;
    prim[1]=false;
    for(int i=2;i<=maxi;i++)
    {
        for(int j=2*i;j<=maxi;j+=i)
        {
            if(prim[j])
                prim[j]=false;
        }
    }
    for(int i=2;i<=maxi;i++)
    {
        if(prim[i])
        {
            nrdiv[i]=1;
            for(int j=2*i;j<=maxi;j+=i)
            {
                nrdiv[j]++;
            }
        }
    }
    for(int i=1;i<=maxi;i++)
    {
        if(nrdiv[i]<=7)
        {
            a[nrdiv[i]][0]++;
            a[nrdiv[i]][a[nrdiv[i]][0]]=i;
        }
    }
}
int BINARY(int n,int k)
{
    int st=1;
    int dr=a[k][0];
    int val=0;
    while(st<=dr)
    {
        int mid=(st+dr)>>1;
        if(a[k][mid]==n)
        {
            if(val<a[k][mid])
            val=a[k][mid];
            break;
        }
        else{
            if(a[k][mid]>n)
                dr=mid-1;
            else {
                    if(val<a[k][mid])
                     val=a[k][mid];
                    st=mid+1;
            }

        }
    }
    return val;
}
int main()
{
    CIURULETZ();
    f>>t;
    for(int i=1;i<=t;i++)
    {
        f>>n>>k;
        g<<BINARY(n,k)<<'\n';
    }
    return 0;
}