#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
bool prim[100002];
ll t, n, k;
ll v[1000002], d[8], a[8][1000002];
void ciur()
{
    for(ll i=3; i<1000002; i+=2)
    {
        if(!prim[i])
        {
            v[i]=1;
            for(ll j=2*i; j<1000002; j+=i)
            {
                prim[j]=1;
                v[j]++;
            }
        }
    }
    for(ll i=2; i<1000002; i++)
    {
        if(!(i&1))
            v[i]++;
        d[v[i]]=i;
        for(ll j=1; j<=7; j++)
            a[j][i]=d[j];
    }
}
int main()
{
    f>>t;
    ciur();
    while(t)
    {
        f>>n>>k;
        g<<a[k][n]<<'\n';
        t--;
    }
    f.close();
    g.close();
    return 0;
}