#include <iostream>
#include <fstream>
using namespace std;

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

///d[i] = nr de divizori primi pt i
bool c[1000001];
int d[1000001];
int m[8][400000];

int main()
{

    cout << sizeof(c) / 1024.0 / 1024.0;

    int n, t, k, st, dr, mij;

    c[2] = 1;
    for(int i = 3; i <= 1000000; i += 2)
        c[i] = 1;
    for(int i = 3; i * i <= 1000000; i += 2)
        if(c[i] == 1)
            for(int j = i * i; j <= 1000000; j += 2 * i)
                c[j] = 0;

    d[2] = 1;

    for(int i = 4; i <= 1000000; i += 2)
        d[i]++;

    for(int i = 3; i <= 1000000; i += 2)
        if(c[i] == 1)
        {
            for(int j = 2 * i; j <= 1000000; j += i)
                d[j]++;
        }

    for(int i = 2; i <= 1000000; i++)
        if(d[i] <= 7)
            m[ d[i] ][ ++m[d[i]][0] ] = i;

/*
    for(int i = 1; i <= 7; i++)
        cout << i << ": " << m[i][0] << "\n";
*/
    fin >> t;
    for(int i = 1; i <= t; i++)
    {
        fin >> n >> k;
        int rez = -1;
        st = 1; dr = m[k][0];

        if(n > m[k][ m[k][0] ])
            rez = m[k][ m[k][0] ];

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

    return 0;
}

/*
    c[2] = 1;
    for(int i = 3; i <= 100; i += 2)
        c[i] = 1;
    for(int i = 3; i * i <= 100; i += 2)
        if(c[i] == 1)
            for(int j = i * i; j <= 100; j += 2 * i)
                c[j] = 0;
    cout << 2 << " ";
    for(int  i = 3; i <= 100; i += 2)
        if(c[i] == 1)
            cout << i << " ";

// O(n * log n)
*/