#include <bits/stdc++.h>
#define N 1000000

using namespace std;

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

int divv[N+2], ciur[N + 2], f[8];
int mat[8][380000];
int main()
{
    int T,k, x;
    int i, j;
    int st,dr,mij;
    ciur[2] = 1;
    for(i = 3; i <= N; i += 2)
        ciur[i] = 1;
    for(i = 3; i*i <= N; i += 2)
        if(ciur[i] == 1)
            for(j = i * i; j <= N; j += 2 * i)
                ciur[j] = 0;

    for(i = 2; i <= N; i += 2)
        divv[i] = 1;

    for(i = 3; i <= N; i += 2)
        if(ciur[i] == 1)
            for(j = i; j <= N; j += i)
                divv[j]++;

    ///div[i] - cati divizori primi are nr i
    for(i = 1; i <= N; i++)
        if(divv[i] <= 7)
            mat[divv[i]][ ++mat[divv[i]][0] ] = i;

    fin >> T;
    for(i = 1; i <= T; i++)
    {
        fin >> x >> k;
        st = 1;
        dr = mat[k][0];
        int ok = 0;

        while(st <= dr)
        {
            mij = (st + dr) / 2;
            if(mat[k][mij] == x)
                {
                    fout << x << "\n";
                    ok = 1;
                    break;
                }
            else if(mat[k][mij] < x)
                st = mij + 1;
            else if(mat[k][mij] > x)
                dr = mij - 1;

        }
        if(ok == 0)
        {
            if(mat[k][1] > x) fout << 0 << "\n";
            else if(mat[k][st] < x) fout << mat[k][st] << "\n";
            else if(mat[k][st] > x) fout << mat[k][st - 1]<< "\n";
        }
    }


    /// 2 3 4 5 7 8 9 11 13 16

    return 0;
}