#include <bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int lmax = 1000000;
int f[lmax + 1][8], cnt[lmax + 1];
int main()
{
    int n, k, t;
    for(int i = 2; i <= lmax; i ++){
        if(cnt[i] == 0){
            for(int j = i; j <= lmax; j += i){
                cnt[j] ++;
            }
        }
    }
    for(int i = 1; i <= lmax; i ++){
        for(int j = 1; j <= 7; j ++){
            f[i][j] = f[i - 1][j];
        }
        if(cnt[i] <= 7){
            f[i][cnt[i]] = i;
        }
    }
    cin >> t;
    for(int i = 1; i <= t; i ++){
        cin >> n >> k;
        cout << f[n][k] << '\n';
    }

}