//
//  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 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] ++;
            }
        }
    }
    int nrtest;
    cin>>nrtest;
    for (int counter = 1; counter <= nrtest; counter++) {
        cin>>nr>>k;
        int i = nr;
        while (divprim[i] != k) {
            i --;
        }
        if (i >= 0) {
            cout<<i<<"\n";
        } else {
            cout<<"0\n";
        }
    }
    
    return 0;
}