#include <fstream>
#include <vector>

using namespace std;

const int MAX = 1000001;
vector<int> prime[8];
vector<int>::iterator it;
int Ciur[MAX];

int main()
{
    fstream f("divprim.in",ios::in);
    ofstream g("divprim.out");
    int N,K,T,i,j;

    for (i = 2; i < MAX; i++)
    {
        if (Ciur[i] == 0)
            for (j = i; j < MAX; j += i)
                ++Ciur[j];
        prime[Ciur[i]].push_back(i);
    }

   f>>T;
   do
    {
        f>>N>>K;
        if(prime[K][0]>N)g<<"0\n";
        else
            {
            it = lower_bound (prime[K].begin(),prime[K].end(),N);
            --it;
            g<<*it<<"\n";
            }

    }while(--T);
    return 0;
}