#include <bits/stdc++.h>
#define ValMax 1000001

using namespace std;

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

int t;
int n, k;
int ndp[ValMax];

struct Hash
{
    vector<int> v;
};

Hash h[ValMax];

void Ciur()
{
    ndp[0] = 0;
    ndp[1] = 0;
    for ( int i = 2; i < ValMax ; i++ )
        if ( ndp[i] == 0 )
          for ( int j = i; j < ValMax ; j += i)
              ndp[j]++;
}

void Precalc()
{
    for ( int i = 0; i < ValMax; i++ )
        h[ndp[i]].v.push_back(i);
}

int CautaBinar( int n, int k )
{
    int sol = 0;
    int st = 0; int dr = h[k].v.size() - 1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(h[k].v[mij] <= n)
        {
            sol = h[k].v[mij];
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return sol;
}

int main()
{
    Ciur();
    Precalc();
    fin >> t;
    while ( t-- )
    {
        fin >> n >> k;
        fout << CautaBinar(n, k) << '\n';
    }
    return 0;
}