#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int d[N],a[N][8];
int main()
{
    int t,n,k,i,j;
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    for (i=2; i<=N-5; i++)
    {
        if (d[i]==0)
        {
        for (j=i; j<=N-5; j+=i)
            d[j]++;
        }
    }
    for (i=2; i<=N; i++)
    {
        for (j=1; j<=7; j++)
        {
            a[i][j]=a[i-1][j];
        }
        a[i][d[i]]=i;
    }
    cin >> t;
    for (i=1; i<=t; i++)
    {
        cin >> n >> k;
        cout << a[n][k] << "\n";
    }



    return 0;
}