#include <cstdlib>
#include <cstdio>
#define MAX_SIZE 1000001
using namespace std;

int ciur[MAX_SIZE];
int diviz[MAX_SIZE];
int matr[MAX_SIZE][8];

void prims(int maxim)
{
    for (int i =1;i<=maxim;i++)
    ciur[i] = diviz[i] = 0;
    for (int i=2;i<=maxim;i++)
    {
        if (ciur[i] == 0)
        {
            for (int j=0;j<=(maxim / i);j++)
            {
                ciur[j * i] =1;
                diviz[j * i] ++ ;
            }
        }
    }
    for (int i=0;i<maxim;i++)
    {
        for (int j=0;j<8;j++)
        {
            matr[i][j] = matr[i-1][j];
            matr[i][diviz[i]] = i;
        }
    }

}

int main()
{
    FILE *input = fopen("divprim.in","r");
    FILE *output = fopen("divprim.out","w");
    int t;
    fscanf(input,"%d",&t);
    int maxim;
    prims(MAX_SIZE);

    for (int i=0;i<t;i++)
    {
        int x,y;
        fscanf(input,"%d%d",&x,&y);
        fprintf(output,"%d\n",matr[x][y]);
    }
    fclose(input);
    fclose(output);
    return 0;
}