#include <iostream>
#include <cstdio>
using namespace std;

int ww[1000005];
int a[1000005][10];

void ciur()
{
    for(int i = 2; i <= 1000000; i += 2)
        ww[i] = 1;
    for(int i = 3; i <= 1000000; i += 2)
        if(!ww[i])
            for(int j = i; j <= 1000000; j += i)
                ww[j]++;
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ios::sync_with_stdio(false);
    int t; cin >> t;

    ciur();

    for(int i = 1; i <= 1000000; ++i)
    {
        for(int j = 0; j <= 7; ++j)
        {
            if(ww[i] == j)
                a[i][j] = i;
            else a[i][j] = a[i - 1][j];
        }
    }

    int x, y;
    for(int i = 1; i <= t; ++i)
    {
        cin >> x >> y;
        cout << a[x][y] << '\n';
    }
    return 0;
}