#include <stdio.h>

using namespace std;

struct titaniu {int nr,div;};
titaniu ciur[1000001];

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int i,j,x,dr,st,numar,k,mij;
    ciur[1].nr=1;
    ciur[1].div=0;
    for(i=2;i*i<=1000000;i++)
    {
        ciur[i].nr=i;
        if(ciur[i].div==0)
        {
            ciur[i].div=1;
            for(j=i*i;j<=1000000;j+=i)
            {
                ciur[j].div++;
            }
        }
    }
    scanf("%d",&x);
    for(i=1;i<=x;i++)
    {
        scanf("%d %d",&dr,&k);
        while(ciur[dr].div!=k && dr!=0)
        {
            dr--;
        }
        printf("%d\n",dr);
    }

    return 0;
}