#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int t;
vector < vector < int > > m;
vector < int > ndiv;
vector < pair < int, int > > v;
int nmax, kmax;

void citire()
{
    in>>t;
    int n,k;
    v.reserve(t+1);
    for(int i=1;i<=t;i++)
    {
        in>>n>>k;
        v.push_back(make_pair(n,k));
        nmax=max(nmax,n);
        kmax=max(kmax,k);
    }
}

void rezolvare()
{
    int i, j;
    m.resize(kmax+1);
    ndiv.resize(nmax+15,0);
    for(j=2;j<=nmax;j+=2)
        ++ndiv[j];
    for(i=3;i<=nmax;i+=2)
        if(ndiv[i] == 0)
            for(j=i;j<=nmax;j+=i)
                ++ndiv[j];
    for(i=0;i<=kmax;i++)
    {
        m[i].reserve(nmax+1);
        m[i].push_back(0);
    }
    for(i=1;i<=nmax;i++)
        m[ndiv[i]].push_back(i);
}

void afisare()
{
    int i;
    int n,k;
    int inc , sf, mi;
    for(i=0;i<t;i++)
    {
        n=v[i].first;
        k=v[i].second;
        inc=0;
        sf=m[k].end()-m[k].begin()-1;
        while(inc<sf)
        {
            mi=(inc+sf)/2;
            if(m[k][mi]==n)
                inc=sf=mi;
            else if(n>m[k][mi])
                inc=mi+1;
            else
                sf=mi-1;
        }
        while (n<m[k][inc])
            inc--;
        while(n>m[k][inc+1] && inc<m[k].begin()-m[k].end())
            inc++;
        out<<m[k][inc]<<'\n';
    }
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}