#include <bits/stdc++.h>
#define MX 1000005
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int prim[MX][9];
int main()
{
    int n,x,y;
    f>>n;
    //vector<vector<int> > prim(MX+5, vector<int>(9,0));
    //int prim[MX][9];
    for(int i=2; i<=MX; ++i){
        if(prim[i][8]==0){
            for(int j=i; j<=MX; j+=i){
                prim[j][8]++;
            }
        }
    }
    for(int i=2; i<=MX; ++i){
        for(int j=0; j<8; ++j){
            if(prim[i][8]==j)   prim[i][j]=i;
            else prim[i][j]=prim[i-1][j];
        }
    }
    while(n--){
        f>>x>>y;
        g<<prim[x][y]<<"\n";
    }
    return 0;
}