#include<bits/stdc++.h>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");
#define NMAX 1000005


vector<int> v[8];

int prime[NMAX];

void era()
{
    prime[0] = prime[1] = 0;
    for(int i=2;i<=1000000;i++)
    {
        if(prime[i] == 0)
        {
            for(int j = i;j<=1000000;j+=i)
            {
                prime[j]++;
            }
        }
    }
}

int cauta(int k,int nr)
{
    int dr = v[k].size()-1;
    int st = 0;
    int sol = 0;

    while(st<=dr)
    {
        int m = (st+dr)/2;
        if(v[k][m] <= nr)
        {
            sol = v[k][m];
            st = m + 1;
        }
        else
        {
            dr = m-1;
        }
    }

    return sol;
}

int main() {

    era();
    int maxim = 0;
    for(int i=0;i<=1000000;i++)
    {
        int idx = prime[i];
        v[idx].push_back(i);
    }



    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int nr,k;
        fin>>nr>>k;
        fout<<cauta(k,nr)<<'\n';
    }


}