#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

const int NMAX = 1000005;

int T, N, K;
bool Prime[NMAX];
vector<int> P, List[9];

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);

    for(int i = 2; i < NMAX; ++ i)
        if(!Prime[i])
        {
            P.push_back(i);
            for(int j = i + i; j < NMAX; j += i)
                Prime[j] = 1;
        }

    for(int i = 1; i < NMAX; ++ i)
    {
        int Cnt = 0, Temp = i;
        for(int j = 0; P[j] * P[j] <= Temp; ++ j)
            if(Temp % P[j] == 0)
            {
                Cnt ++;
                while(Temp % P[j] == 0) Temp /= P[j];
            }
        if(Temp > 1) Cnt ++;
        List[Cnt].push_back(i);
    }

    scanf("%i", &T);
    for(; T; T --)
    {
        scanf("%i %i", &N, &K);
        int Ans = 0, Step = (1 << 19);
        for(; Step; Step /= 2)
            if(Ans + Step < List[K].size() && List[K][Ans + Step] <= N)
                Ans += Step;
        if(List[K][Ans] <= N) printf("%i\n", List[K][Ans]);
        else printf("0\n");
    }

    return 0;
}