#include <fstream>
#include <iostream>

using namespace std;

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

int d[1000002];

bool ciur[1000002];

void Ciur()
{
    int i, j;
    ciur[2] = 1;
    for(i = 3; i <= 1000000; i += 2)
        ciur[i] = 1;
    for(i = 2; i <= 1000000; i += 2)
        d[i] = 1;
    
    for(i = 3; i <= 1000000; i += 2)
        if(ciur[i] == 1)
            for(j = i; j <= 1000000; j += i)
            {
                d[j]++;
                if(j != i)
                    ciur[j] = 0;
            }
}

int n, t, k;

int mat[8][342000];

int main()
{
    int i, x, y, st, dr, rez, mij;
    fin >> n;
    Ciur();
   //for( i = 1; i<= 15; i++)
   //cout << d[i] << " ";
   for(i = 1; i <= 1000000; i++)
        if(d[i] <= 7)
            {
                mat[d[i]][0]++;
                mat[d[i]][ mat[d[i]][0] ] = i;
            }
    for(i = 1; i <= n; i++)
        {
            fin >> x >> y;
            st = 1;
            dr = mat[y][0];
            if(x < mat[y][1]) rez = 0;
            if(x > mat[y][1]) rez = mat[y][dr];
            while(st <= dr)
            {
                mij = st + (dr - st) / 2;
                if(mat[y][mij] == x)
                {
                    rez = x;
                    break;
                }
                else if(mat[y][mij] > x)
                    dr = mij - 1;
                else
                {
                    rez = mat[y][mij];
                    st = mij + 1;
                }
            }
            fout << rez << "\n";
        }
    return 0;
}