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

const int NMAX = 1000005;

int T, N, K, Fact[NMAX];
vector<int> List[9];

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

    List[0].push_back(1);
    for(int i = 2; i < NMAX; ++ i)
    {
        if(!Fact[i])
        {
            Fact[i] = 1;
            for(int j = i + i; j < NMAX; j += i)
                Fact[j] ++;
        }
        List[Fact[i]].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;
}