#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX 1000001

FILE *f, *g;

using namespace std;
int d[MAX], rez[MAX][8];
struct intrb
{
    int lim, div, poz, rez;
};
intrb v[MAX];
int comp(intrb i, intrb j)
{
    return i.div < j.div;
}
int comp2(intrb i, intrb j)
{
    return i.poz < j.poz;
}
void nrdiv()
{
    int i, j;
    for(i = 2; i < MAX; i++)
        if (d[i] == 0)
            for(j = i; j < MAX; j += i)
                d[j]++;

}

int main()
{   int n, aux, i;
    f = fopen("divprim.in", "r");
    fscanf(f, "%d", &n);
    nrdiv();
    g = fopen("divprim.out", "w");
    /*for(i = 1; i <= n; i++)
    {
        fscanf(f, "%d%d", &v[i].lim, &v[i].div);
        v[i].poz = i;
    }
    sort(v + 1, v + n + 1, comp);
    i = 1;
    int j = 0;
    aux = v[i].div;
    while(i <= n)
    {
        while(aux == v[i].div)
        {
            while(j <= v[i].lim)
            {
                if(d[j] == v[i].div)
                    v[i].rez = j;
                j++;
            }
            i++;

        }
        aux = v[i].div;
        j = 0;
    }
    sort(v + 1, v + n + 1, comp2);
    for(i = 1; i <= n; i++)
    {
        fprintf(g, "%d\n", v[i].rez);
    }*/


    for ( int i = 1; i <= MAX; ++i ){
        for ( int j = 1; j <= 7; ++j ){
            rez[i][j] = rez[i-1][j];
            rez[i][d[i]] = i;
        }
    }
    int x, y;
    for(i = 1; i <= n; i++)
    {
        fscanf(f, "%d%d", &x, &y);
        fprintf(g, "%d\n", rez[x][y]);
    }
    fclose(f);
    fclose(g);
    return 0;
}