#include <cstdio>

using namespace std;
int c[1000005];
void ciur(int n)
{
    for(int i = 2 ; i <= n ; i += 2)
      c[i] = 1;
    for(int i = 3 ; i <= n ; i += 2)
    {
        if(c[i] == 0)
          for(int j = i ; j <= n ; j += i)
            c[j]++;
    }
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur(1000000);
    int T , n , k ;
    scanf("%d",&T);
    for(int i = 1 ; i <= T ; i++)
    {
        scanf("%d%d",&n,&k);
        int ans = 0;
        for(int i = n ; i >= 2 ; i--)
          if(c[i] == k)
            {
              ans = i;
              break;
            }
        printf("%d\n",ans);
    }
    return 0;
}