#include <stdio.h>
#include <stdlib.h>
  
#define NMAX 1000000
#define KMAX 7
#define SQRTNMAX 1000
#define PRIME 0
#define CNT   1
  
int T, N, K, i, j, a, b, ind, mid;
int prim[NMAX+5], k_prim[KMAX+1][NMAX+5], cnt[KMAX+1];
  
int cmp(const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
  
void ciur()
{
    for (i = 2; i <= NMAX; i++)
        if (!prim[i])
        {
            prim[i]++;
            for (j = i<<1; j <= NMAX; j += i)
            {
                prim[j]++;
            }
        }
  
    for (i = 2; i <= NMAX; i++)
            k_prim[prim[i]][++cnt[prim[i]]] = i;
    k_prim[0][++cnt[prim[0]]] = 1;
  
    /*for (i = 1; i <= KMAX; i++)
        printf("cu %d dvp:%6d  1st = %6d, 2nd = %6d blast = %6d last = %d\n", i, 
                                                                                      cnt[i],
                                                                                      k_prim[i][1],
                                                                                      k_prim[i][2],
                                                                                      k_prim[i][cnt[i]-1],
                                                                                      k_prim[i][cnt[i]]
                                                                                      );*/
    //    qsort(&k_prim[i][1], cnt[i], sizeof(int), cmp);
    //getchar();
}
  
  
int main()
{
    FILE *in, *out;
    in =  fopen("divprim.in", "r");
    out = fopen("divprim.out", "w");
    fscanf(in, "%d\n", &T);
      
    ciur();
  
    while(T)
    {
        fscanf(in, "%d %d\n", &N, &K);
        if (K == 0)
            fprintf(out, "%d\n", 1);
        else
        {
            a = 1;
            b = cnt[K];
            ind = 0;
            while (b - a >= 10)
            {
                mid = (a + b)>>1;
                if (k_prim[K][mid] < N)
                    a = mid + 1;
                else if (k_prim[K][mid] > N)
                    b = mid - 1;
                else
                {
                    ind = mid;
                    break;
                }
            }
            //printf("a = %d\n", a);
            if (!ind)
            {
                for (i = a; i <= b && k_prim[K][i] < N; i++);
                //printf("i = %d\n", i);
                
                if (k_prim[K][i] == N)
                    ind = i;
                else if (k_prim[K][i] > N)
                    ind = i > 1 ? i-1 : 0;
                else
                {
                    ind = i > 2 ? i - 1 : 0;
                }
            }
             
            fprintf(out, "%d\n", k_prim[K][ind]);
        }
        T--;
    }
  
  //getchar();
    fclose(in);
    fclose(out);
    return 0; 
}