#include <iostream>
using namespace std;
int ciur[10000001];
int a[9][10000001];

int cb(int v[], int n,  int st, int dr)
{
    int p = -1;
    while (st <=dr)
   {
       int mij = (st + dr)/2;
       if (v[mij]  == n)
           return v[mij];
       if (v[mij] < n)
       { //nr mai mic decat  n
        if (mij > p)
            p = mij;
        st = mij+1;
       }
       else
        dr = mij - 1;
        //vr mai mic
     }
    return v[p];
}
void f()
{
    int m = 0;
    for (int i = 2; i <= 1000000; i++)
    {
        if (ciur[i] == 0)
        {
            for (int j = 2; j * i <= 1000000; j++)
            {
                ciur[j * i] += 1;
                if (ciur[j * i] > m)
                {
                    m = ciur[j * i];
                }
            }
        }
    }
   // cout << m << endl;// varianta 2 la codul de mai jos
    int k;
   // for (int j = 0; j < 8; j++)// doar ca este mai lunga. caci parcurgem sirul de numere ciur si cautam toate numerele care au j=0 divizori primi si le punem pe linia 0
   // { // apoi j=1 - toate numerele ce au un divizor prim se pun pe lin ia 1 etc.
        // k = 1;
        // for (int i = 2; i <= 1000000; i++)
        // {
        //     if (ciur[i] == j)
        //     {
        //         a[j][k++] = i;
        //     }
        // }
        // a[j][0] = k - 1;


   // }
   for (int i = 2; i <= 1000000; i++) // luam fiecare numar intre 2 si 1 milion si vedem pe ce linie trebuie pus in matricea a, varianta 1
   {
    //cout<<ciur[i]<<endl;
    int c = a[ciur[i]][0]; // pe linia ciur[i] exista c numere care au ciur[i] divizori primi
    c++; // crestem c si punem valoarea noua in a[ciur[i]][0] si apoi
    a[ciur[i]][0] = c;
    a[ciur[i]][c] = i; // la pozitia a[ciur[i]][c] punem si numarul i ce are ciur[i] divizori primi
   }
    // for (int i = 0; i<8; i++) // pe linia i sunt numerele care au i divizori primi. Numarul de numere care au i divizori primi se gaseste in a[i][0]
    //     cout<<a[i][0]<<' ';

}
int main()
{
    int n, k, m, mij,t;
    cin >>t;
    f();
    for(int i=1;i<=t;i++)
     {
      cin>> n >> k;
       cout<<cb(a[k], n,1,a[k][0])<<endl;// cautam binar pe linia k - adica a[k] - care de fapt se poate vedea ca un vector de la prima coloana st=1 pana la ultima
       // coloana adica dr=a[k][0] un numar care sa fie <=n si sa aiaba k divizori primi
       // facem cautare binara deoarece pe fiecare linie sunt multe numere si in plus acestea au fost plasate in ordine crescatoare
     }
    return 0;
}