#include <bits/stdc++.h>

#define key 7

using namespace std;

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

int v[1000010], N, T, K;
vector<int>Map[key];

void ciur()
{
    for(int i = 2; i <= 1000000; i ++)
    {
        if(v[i] == 0)
        {
            for(int j = i; j <= 1000000; j += i)
            {
                v[j] ++;
            }
        }
        Map[v[i]].push_back(i);
    }
}



int main()
{
    fin >> T;

    ciur();

    while(T --)
    {
        fin >> N >> K;

        int solution = upper_bound(Map[K].begin(), Map[K].end(), N) - Map[K].begin() - 1;
        if(solution  < 0)
        {
            fout << 0 << '\n';
        }
        else
        {
            fout << Map[K][solution] << '\n';
        }


    }
    return 0;
}