#include<iostream>
using namespace std;
#include<stdio.h>
FILE *f,*g;
int a[1000001][8],v[1000001],i,j,n,k,q;
int main()
{
    f=fopen("divprim.in","r");
    g=fopen("divprim.out","w");
    for(i=2;i<=1000000;i++)
        if(v[i]==0)
    {v[i]=1;
        for(j=i+i;j<=1000000;j=j+i)
            v[j]=v[j]+1;
    }
    for(i=1;i<=1000000;i++)
        a[i][v[i]]=i;
    for(i=1;i<=1000000;i++)
        for(j=1;j<=7;j++)
        if(a[i][j]<a[i-1][j])
        a[i][j]=a[i-1][j];
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d %d",&k,&q);
        fprintf(g,"%d\n",a[k][q]);
    }

}