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

#define nmax 1000000

int c[nmax + 1], v[nmax + 1], p[nmax + 1][8];
int T, N, K;

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    int i, j;
    for(i = 2; i <= nmax; i++)
          if(!v[i])
          {
                   c[i] = 1;
                   for(j = 2 * i; j <= nmax; j += i)
                   {
                         ++ c[j];
                         v[j] = 1;
                   }
          }
    for(i = 1; i <= nmax; i++)
    {
          for(j = 0; j < 8; j++)
                p[i][j] = p[i - 1][j];
          if(c[i] <= 7)
                  p[i][c[i]] = i;
    }
    scanf("%i", &T);
    while(T --)
    {
            scanf("%i %i", &N, &K);
            printf("%i\n", p[N][K]);
    }
    return 0;
}