#include <fstream>
#include <algorithm>

using namespace std;

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

long long ciur[1000001];
long long nrdiv[1000001];
long long v[8][100001];

int main()
{
    int n, p1 = 0, p2 = 0, p3 = 0, p4 = 0, p5 = 0, p6 = 0, p7 = 0, t, k,st, dr, mij = 1, sol = 0;
    fin >> n;
    ciur[2] = 1;
    for(int i = 3; i <= 1000000; i += 2)
        ciur[i] = 1;
    for(int i = 3; i * i <= 1000000; i += 2)
    {
        if(ciur[i] == 1)
        {
            for(int j = i * i; j <= 1000000; j += 2 * i)
                ciur[j] = 0;
        }
    }
    for(int i = 2; i <= 1000000; i++)
    {
        if(ciur[i] != 0)
        {
            for(int j = i; j <= 1000000; j += i)
                nrdiv[j]++;
        }
    }
    for(int i = 1; i <= 1000000; i++)
    {
        if(nrdiv[i] == 1)
        {
            p1++;
            v[nrdiv[i]][p1] = i;
        }
        else if(nrdiv[i] == 2)
        {
            p2++;
            v[nrdiv[i]][p2] = i;
        }
        else if(nrdiv[i] == 3)
        {
            p3++;
            v[nrdiv[i]][p3] = i;
        }
        else if(nrdiv[i] == 4)
        {
            p4++;
            v[nrdiv[i]][p4] = i;
        }
        else if(nrdiv[i] == 5)
        {
            p5++;
            v[nrdiv[i]][p5] = i;
        }
        else if(nrdiv[i] == 6)
        {
            p6++;
            v[nrdiv[i]][p6] = i;
        }
        else if(nrdiv[i] == 7)
        {
            p7++;
            v[nrdiv[i]][p7] = i;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        fin >> t >> k;
        if(k == 1)
            dr = p1;
        else if(k == 2)
            dr = p2;
        else if(k == 3)
            dr = p3;
        else if(k == 4)
            dr = p4;
        else if(k == 5)
            dr = p5;
        else if(k == 6)
            dr = p6;
        else if(k == 7)
            dr = p7;
	st = 1;
        while(st <= dr)
        {
            mij = (st + dr) / 2;
            if(v[k][mij] <= t)
            {
                st = mij + 1;
                sol = v[k][mij];
            }
            else
                dr = mij - 1;
        }
            fout << sol << "\n";
    }
    return 0;
}