#include <iostream>
#include <fstream>
#define N 100001
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");


int nrd[N];
int a[8][N];
int C[N];

void Ciur()
{
    int i, j;
    C[2] = 1;
    for(i = 3; i <= N; i+= 2)
        C[i] = 1;
    for(i = 3; i*i <= N; i+= 2)
       if(C[i] == 1)
            for(j = i*i; j <=N; j+= i)
                C[j] = 0;


}
void Nrd()
{
    int i, j;
    Ciur();

    for(i = 2; i <= N; i++)
        if(C[i] == 1)
            for(j = i; j <= N; j+= i)
                nrd[j]++;
}
void Constr()
{
    int i, j;
    for(i = 1; i <= N; i++)
        if(nrd[i] <= 7)
            a[nrd[i]][++a[nrd[i]][0]] = i;
}
int main()
{
    int T, x, nr, st, dr, mij;
    bool gasit;
    Nrd();
    Constr();
    fin >> T;
    for(int i = 1; i <= T; i++)
    {
        fin >> x >> nr;
        gasit = 0;
        if(a[nr][1] > x) fout << 0 << "\n";
        else
        {
        st = 1;
        dr = a[nr][0];
        while(st <= dr)
        {
            mij = st + (dr - st)/2;
            if(a[nr][mij] == x) {fout << x << "\n"; gasit = 1; break;}
            else if(a[nr][mij] < x) st = mij + 1;
                else dr = mij - 1;
        }
        if(gasit == 0)
        {

            if(a[nr][st] < x) fout << a[nr][st] << "\n";
            else fout << a[nr][st-1] << "\n";
        }
        }
        //fout << a[nr][mij] << "\n";



    }
    return 0;
}