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

FILE *f, *g;

using namespace std;
int d[MAX], rez[8][MAX];
/*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);
    }*/

/*
rez[1]: 2,3,4,5,7,8,9,11....
rez[2]: 6,10,12,15,18...
rez[3]: 30,....
*/
    for ( i = 1; i < MAX; i++)
        rez[d[i]][i] = i;
    for (i = 1; i <= 7; i++)
        for (int j = 1; j < MAX; j++)
            if (rez[i][j] == 0)
                rez[i][j] = rez[i][j-1];

    /*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[y][x]);
    }
    fclose(f);
    fclose(g);
    return 0;
}