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

int main()
{
    ifstream fin ("divprim.in");
    ofstream fout ("divprim.out");
    int t;
    fin >> t;
    for (int a=1;a<=t;a++){
        int n,k;
        fin >> n;
        fin >> k;
        char prim[n+1];
        for (int b=2;b<=n;b++){
            prim[b]=0;
        }
        int c=2;
        while (c!=n){
            if (prim[c]==0){
                for (int d=c;d<n;d=d+c){
                    prim[d]++;
                    if (prim[d]==k){
                        fout << d << endl;
                        c=n+1;
                        d=n+1;
                    }
                }
                c++;
            }
        }
        if (c==n){
            fout << "0" << endl;
        }
    }

    return 0;
}