#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 search()
{
    long long i, pas = 1 << 15;

    for(i = 0; pas != 0; pas /= 2)
        if(i + pas < a[K].size() && a[K][i + pas] <= N)
            i += pas;
    return i;
}

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;
        int s = search();
        if(a[K][s] <= N) g << a[K][s] << "\n";
        else g << "0\n";
    }
}