#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
#define MAX 1000010
int b[MAX+10];
int a[MAX+10][9];

void ciur()
{
    int i,j;
    for(i=2;i<=MAX;i+=2)
    {
        b[i]++;
    }
    for(i=3;i*i<=MAX;i+=2)
    {
        if(!b[i])
        {
            for(j=i;j<=MAX;j+=i)
            {
                b[j]++;
            }
        }
    }
}

int main()
{
    int n, x, y, i, j;
    ciur();
    for(i=1;i<=MAX;i++)
    {

        for(j=0;j<=7;j++)
        {
            a[i][j]=a[i-1][j];
        }
        a[i][b[i]]=i;
    }

    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        fout<<a[x][y]<<"\n";
    }
}