#include <bits/stdc++.h>
#define NMAX 1000005
using namespace std;

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

int d[NMAX];
bitset<NMAX> ciur;
int M[8][NMAX];
int n , t , k;

int main()
{
    int i , j;
    ciur[1] = 1;
    for(i = 4 ; i <= NMAX ; i += 2)
        ciur[i] = 1;
    for(i = 3 ; i * i <= NMAX ; i += 2)
        if(ciur[i] == 0)
            for(j = i * i ; j <= NMAX ; j += i)
                ciur[j] = 1;
    for(i = 2 ; i <= NMAX ; i++)
        if(ciur[i] == 0)
            for(j = i ; j <= NMAX ; j += i)
                d[j]++;
    for(i = 2 ; i <= NMAX ; i++)
    {
        M[d[i]][++M[d[i]][0]] = i;
        ///cout << i << " " << d[i] << " " << M[d[i]][0] << "\n";
    }
    int st , dr , mij , rez;
    fin >> t;
    while(t--)
    {
        fin >> n >> k;
        if(n < M[k][1]) fout << "0\n";
        else if (n >= M[k][M[k][0]]) fout << M[k][M[k][0]];
        else
        {
            st = 1;
            dr = M[k][0];
            rez = 0;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(M[k][mij] > n) dr = mij - 1;
                else
                {
                    rez = M[k][mij];
                    st = mij + 1;
                }
            }
            fout << rez << "\n";
        }
    }
    return 0;
}