#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int N_MAX=1e6;
const int NUMBERS_MAX=379720;
const int K_MAX=7;
char sieve[N_MAX+1]{};
int m[K_MAX+1][NUMBERS_MAX], len[K_MAX+1]{};

void Eratosthenes(){
    for(int d=2; d<=N_MAX; ++d)
        if(!sieve[d])
            for(int i=d; i<=N_MAX; i+=d)
                ++sieve[i];
}

void RearrangeNumbers(){
    for(int i=0; i<=K_MAX; ++i)
        m[i][len[i]++]=0;
    for(int i=1; i<=N_MAX; ++i)
        m[sieve[i]][len[sieve[i]]++]=i;
}

int BinarySearch(int v[], int n, int val){
    int b=0, e=n, mid; ///[b;e)
    while(e-b>1){
        mid=(b+e)/2;
        if(v[mid]<=val)
            b=mid;
        else
            e=mid;
    }
    return v[b];
}

int main(){
    Eratosthenes();
    RearrangeNumbers();

    int t, n, k;
    fin>>t;
    for(int i=0; i<t; ++i){
        fin>>n>>k;
        fout<<BinarySearch(m[k], len[k], n)<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}