#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 Nrd()
{
    int i, j;
    for(i = 2; i <= N; i++)
        if(nrd[i] == 0)
            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;
}