#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,i,j,n,k,ciur[1000001],a[8][1000001];
void precal(int k)
{
    int m=0;
    for(int i=2; i<=1000001; i++)
    {
        if(ciur[i]==k) m=i;
        a[k][i]=m;
    }
}
int main()
{
    fin>>t;
    for(i=2; i<=1000001; i+=2) ciur[i]++;
    for(i=3; i<1000001; i+=2)
    {
        if(ciur[i]==0)
        {
            for(j=i; j<=1000001; j+=i)
            {
                ciur[j]++;
            }
        }
    }

    for(i=1; i<=7; i++) precal(i);
    for(i=1; i<=t; i++)
    {
        fin>>n>>k;
        fout<<a[k][n]<<'\n';

    }
    return 0;
}