#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");


const unsigned int N_LIMIT = 1000001, K_LIMIT = 9;
unsigned int N, K, d[N_LIMIT], T;
vector <int> a[K_LIMIT];

void div_prim()
{
    for(size_t i = 2; i < N_LIMIT ; i++)
        if(d[i] == 0)
            for(size_t j = i; j < N_LIMIT; j += i)
                d[j]++;
}

void scrie()
{
    for(int i=1 ; i<K_LIMIT ; i++)
    {
        for(int j=0 ; j<a[i].size() && j < 100 ; j++) g << a[i][j] << "\t";
        g << "\n";
    }
}

int main()
{
    f >> T;

    div_prim();

    for(size_t i = 0; i < N_LIMIT; i++)
        a[d[i]].push_back(i);

    scrie();

    //return 0;

    for(unsigned int i = 0; i < T; i++)
    {
        f >> N >> K;
        cout << *lower_bound(a[K].begin(), a[K].end(), N) - 1 << "\n";
    }
}