#include <iostream>
#include <fstream>
#include <vector>
#define nmaxi 1000005

using namespace std;

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

int t,k,n,ct,prim[80000],diviz[nmaxi];
bool er[nmaxi];
vector <int> v[10];

int main()
{
    int i,j;
    er[0]=er[1]=1;
    for(i=2;i<nmaxi;i++) //marcam cu 1 numerele neprime
        if(!er[i])
            for(j=2*i;j<nmaxi;j+=i)
                er[j]=1;
    prim[++ct]=2;
    for(i=3;i<nmaxi;i+=2) //salvam toate numerele prime intr-un vector
        if(!er[i])
            prim[++ct]=i;
    for(i=1;i<=ct;i++) //parcurgem toate numerele prime
        for(j=prim[i];j<nmaxi;j+=prim[i]) //crestem cu 1 numarul de divizori primi ai multiplilor lui prim[i]
            diviz[j]++;
    for(i=1;i<nmaxi;i++) //salvam impreuna pe acelasi "nivel" intr-un vector toate numerele cu acelasi numar de divizori primi
        v[diviz[i]].push_back(i);
    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        int st=0,dr=v[k].size()-1,raspuns=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(v[k][mij]<=n)
            {
                raspuns=v[k][mij];
                st=mij+1;
            }
            else dr=mij-1;
        }
        fout<<raspuns<<endl;
    }
}