#include <bits/stdc++.h>
#define N 1000000
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");
int d[N+5],n,a[N+5][10];
int main()
{
    int i,j,x,k;
    fin >> n;
    for (i=2; i<=N; i++)
    {
        if (d[i]==0)
        for (j=i; j<=N; j+=i)
        d[j]++;
    }
    for (i=2; i<=N; i++)
    {
        for (j=0; j<=7; j++)
            a[i][j]=a[i-1][j];
        a[i][d[i]]=i;
    }
    while (n--)
    {
        fin >> x >> k;
        fout << a[x][k] << "\n";
    }


    return 0;
}