#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
///a[i][j]- nr maxim din interval (1,i) cu exact j divizori
int a[1000005][8],v[1000005];
int main()
{
    int k,i,j,n,x,y;
    n=1000000;
    ///v[i]-nr de factori primi ai lui i
    for(i=2;i<=n;i++)
        if(v[i]==0)
        for(j=i;j<=n;j+=i)v[j]++;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=7;j++)
            if(v[i]==j)a[i][j]=i;
        else a[i][j]=a[i-1][j];
    }
    fin>>k;
    while(k--)
    {
        fin>>x>>y;
        fout<<a[x][y]<<'\n';
    }
    return 0;
}