#include <iostream>
#include <fstream>

using namespace std;

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

bool ciur[1000001];
int d[1000001];
int M[8][380000];

int main()
{
    int n, T, k;

    ciur[2] = 1;

    // numerele impare au sansa de a fi prime

    for(int i = 3; i <= 1000000; i = 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 = j + 2 * i)
                ciur[j] = 0;

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

    for(int i = 3; i <= 1000000; i = i + 2)
        if(ciur[i] == 1)
            for(int j = i; j <= 1000000; j = j + i)
                d[j]++;

    // d[i] = cati divizori primi are numarul i

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

    int maxi = 0, st, dr;
    for(int i = 1; i <= 7; i++)
        if(M[i][0] > maxi)
            maxi = M[i][0];

    cout << maxi;

    fin >> T;
    for(int i = 1; i <= T; i++)
    {
        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];
            int rasp = -1;
            while(st <= dr)
            {
                int mij = (st + dr) / 2;
                if(M[k][mij] > n)
                    dr = mij -1;
                else
                {
                    rasp = M[k][mij];
                    st = mij + 1;
                }
            }
            fout << rasp << "\n";
        }
    }

    return 0;
}