#include <cstdio>
#include <vector>

using namespace std;

const int m=1000001;

FILE *f=fopen("divprim.in","r"),*g=fopen("divprim.out","w");
int divizori[m];
vector <int> div[8];

int main()
{
    for(int i=2;i<m;i++)
        if(divizori[i]==0)
        {
            divizori[i]++;     //numerele prime au 1 factor prim si se creste numarul de divizori ai multiplilor lor
            for(int j=i+i;j<m;j+=i)
                divizori[j]++;
        }
    for(int i=0;i<m;i++)
    {
        div[divizori[i]].push_back(i);
    }
    int n,M,k,l,mid,r,sol;
    fscanf(f,"%i",&n);
    for(int i=0;i<n;i++)
    {
        fscanf(f,"%i %i",&M,&k);
        l=1;
        r=div[k].size();
        sol=0;
        while(l<r)
        {
            mid=l+(r-l)/2;
            if(div[k][mid]==M)
            {
                sol=div[k][mid];
                break;
            }
            if(div[k][mid]<M)
                l=mid+1;
            else
                r=mid-1;
        }
        mid=l+(r-l)/2;
        if(div[k][mid-1]<=M)
            sol=div[k][mid-1];
        fprintf(g,"%i\n",sol);
    }
    return 0;
}