#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

const int NMAX = 1000000;

int _div[NMAX+5], sol[8][NMAX+5];

int main() {
    for(int i=1;i<=NMAX;i++)
        _div[i]=0;
    for(int d=2;d<=NMAX;d++)
    {
        if(_div[d]==0)
        {
            for(int j=d;j<=NMAX;j+=d)
                _div[j]++;
                
        }
    }
    
    for(int p=0;p<=7;p++)
    {
        int solution=0;
        for(int i=1;i<=NMAX;i++)
        {
            if(_div[i]==p)
                solution=i;
            
            sol[p][i]=solution;
        }
            
    }
    
    int h; f>>h;
    for(int i=1;i<=h;i++)
    {
        int r, y; f>>r>>y;
        g<<sol[y][r]<<'\n';
    }
        
    
    
        


    return 0;
}