#include <iostream>
#include <fstream>
#define nmx 1000005
#include <vector>
using namespace std;
int n,t,dv[nmx],k,x,pr[80000],ct;
bool er[nmx];
vector <int> v[10];
int main()
{
    ifstream f ("divprim.in");
    ofstream g ("divprim.out");
    er[0]=er[1]=1;
    for (int i=4; i<nmx; i+=2) er[i]=1;
    for (int i=3; i*i<nmx; i+=2)
        if (!er[i])
            for (int j=i*i; j<nmx; j+=2*i)
                er[j]=1;
    for (int i=2; i<nmx; i++)
        if (!er[i]) pr[++ct]=i;
    for (int i=1; i<=ct; i++)
        for (int j=pr[i]; j<nmx; j+=pr[i])
            dv[j]++;
    for (int i=1; i<nmx; i++)
        v[dv[i]].push_back(i);
    f>>t;
    for (int i=1; i<=t; i++)
    {
        f>>x>>k;
        int st=0,dr=v[k].size()-1,mid,sol=0;
        while (st<=dr)
        {
            mid=(st+dr)/2;
            if (v[k][mid]<=x)
            {
                sol=v[k][mid];
                st=mid+1;
            }
            else dr=mid-1;
        }
        g<<sol<<'\n';
    }
}