#include <fstream>

using namespace std;

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

int ciur[1000002];
int val[1000002][10];

int main()
{
    for(int i=2; i <= 1000000; i++)
    {
        if(ciur[i] == 0)
        {
            ciur[i]++;
            for(int j = 2*i; j<= 1000000; j+=i)
                ciur[j]++;
        }
    }
    for(int i = 2;i <= 1000000; i++)
        for(int j = 1; j <= 7; j++)
            if(ciur[i] == j)
                val[i][j] = i;
            else
                val[i][j] = val[i-1][j];
    int n,t,k;
    fin >> t;
    for(int i=1; i<=t;i++)
    {
        fin >> n >> k;
        fout << val[n][k] << "\n";
    }

    return 0;
}