#include <bits/stdc++.h>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int NMAX = 1000005;
int ciur[NMAX];
int rasp[NMAX][9];

int main()
{
    for(int i=2;i<=NMAX-5;i++)
    {
        if(ciur[i]==0)
        {
            ciur[i]=1;
            for(int j=2*i;j<=NMAX-5;j+=i)
                ciur[j]++;
        }
    }
    for(int i=2;i<=NMAX-5;i++)
    {
        if(ciur[i]<=7) rasp[i][ciur[i]]=i;
        for(int j=1;j<=7;j++)
            if(j!=ciur[i]) rasp[i][j]=rasp[i-1][j];
    }
    int T,n,k;
    fin >> T;
    for(int t=1;t<=T;t++)
    {
        fin >> n >> k;
        fout << rasp[n][k] << '\n';
    }
    return 0;
}