#include<iostream>
#include<cstdio>
const int NMAX = 1000005;
int v[NMAX], nr[NMAX][8];

int main()
{
    int T, N, K;
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
   
    for(int i = 2 ; i < NMAX ; i++)
    {
        if(v[i] == 0)
            for(int j = i ; j < NMAX ; j += i)
                v[j]++;
    }
    for(int i = 2 ; i < NMAX ; i++)
    {
        for(int j = 1 ; j <= 7 ; j++)
            nr[i][j] = nr[i - 1][j];
        nr[i][v[i]] = i;
    }
   
    scanf("%d", &T);
    for(int x = 1 ; x <= T ; x++)
    {
        scanf("%d%d", &N, &K);
        printf("%d\n", nr[N][K]);
    }
    return 0;
}