#include <iostream>
#include <fstream>
#define NMAX 1000000
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int ciur[NMAX], maxdiv[NMAX][8];//maxim 7 divizori primi

int main()
{
    for(int i=2;i<NMAX;i+=2)
    {
        ciur[i]++;
    }
    for(int i=3;i<NMAX;i+=2)
    {
        if(ciur[i]==0)
        for(int j=i;j<NMAX;j+=i)
            ciur[j]++;
    }
    for(int i=2;i<NMAX;i++)
    {
        for(int ndv=1;ndv<=7;ndv++)
            maxdiv[i][ndv]=maxdiv[i-1][ndv];//ia numarul precedent pt respectivul nr de divixori
        maxdiv[i][ciur[i]]=i;//updateaza numarul maxim cu v[i]divizori;
    }
    int t;
    in>>t;
    while(t>0)
    {
        t--;
        int n, k;
        in>>n>>k;
        out<<maxdiv[n][k]<<"\n";
    }
    return 0;
}