#include <bits/stdc++.h>

using namespace std;

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

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

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])
        {
            if(mij==0) return 0;
            else dr=mij-1;
        }
        else
        {
            if(mij==dr) return a[mij];
            else if (x>=a[mij+1]) st=mij+1;
            else return a[mij];
        }
    }
    if(x>a[dr]) return a[dr];
    return 0;
}

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

int main()
{
    ciur();
    matrice();
    /**
    for(int i=0; i<=K_max; i++)
    {
        for(int j=0; j<=V_max; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
    **/
    int t;
    fin >> t;
    for(int i=0; i<t; i++)
    {
        sol();
        fout << '\n';
    }
    return 0;
}