#include <bits/stdc++.h>

using namespace std;

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

const int K_max=7;
const int V_max=1e7;

int v[V_max+1];
int m[K_max+1][V_max+1], s[K_max+1];

void ciur()
{
    for(int i=2; i<=V_max; i++)
        if(v[i]==0)
            for(int j=i; j<=V_max; j+=i)
                v[j]++;
}

void matrice()
{
    for(int i=2; i<=V_max; i++)
        if(v[i]<=K_max)
            m[v[i]][s[v[i]]++]=i;
}

int cb(int a[], int x, int dr)
{
    int st=0, mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(x<a[mij]) dr=mij-1;
        else st=mij+1;
    }
    if(a[dr]>x) return 0;
    return a[dr];
}

void sol()
{
    int n, k;
    fin >> n >> k;
    fout << cb(m[k], n, s[k]-1);
}

int main()
{
    ciur();
    matrice();
    int t;
    fin >> t;
    for(int i=0; i<t; i++)
    {
        sol();
        fout << '\n';
    }
    return 0;
}