#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[100002], d[8], a[8][100002];
void ciur()
{
    for(ll i=3; i<100002; i+=2)
    {
        if(!prim[i])
        {
            v[i]=1;
            for(ll j=2*i; j<100002; j+=i)
            {
                prim[j]=1;
                v[j]++;
            }
        }
    }
    for(ll i=2; i<100002; 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--;
    }
    return 0;
}