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

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[j][i]=a[j][i-1];
        }
        a[b[i]][i]=i;
    }

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