//
//  main.cpp
//  Divi3ori Primi
//
//  Created by Andu Andu on 21/10/2019.
//  Copyright © 2019 Andu Andu. All rights reserved.
//

#include <fstream>
#define n 1000005
using namespace std;

ifstream cin ("divprim.in");
ofstream cout ("divprim.out");

int divprim[n];
int v[n][9]; // cel mai apropiat de [] care are [] divizori
int k;
int nr;
int main() {
    
    for (int i=2; i<=n; i++) {
        if (divprim[i] == 0) {
            for(int j=0;j<=n;j+=i) {
                divprim[j] ++;
            }
        }
    }
    
    for (int i=1; i <= n; i++) {
        for (int j=0; j<=7; j++) {
            v[i][j] = v[i-1][j];
        }
        if (divprim[i] <= 7) {
            v[i][divprim[i]] = i;
        }
        
    }
    
    int nrtest;
    cin>>nrtest;
    for (int counter = 1; counter <= nrtest; counter++) {
        cin>>nr>>k;
        cout<<v[nr][k]<<"\n";
    }
    
    return 0;
}