#include<stdio.h>
#define NMAX 1000000

using namespace std;



int v[NMAX+2];
int list[8][NMAX];

int cauta(int w[], int n)
{
    int a=1, b=w[0], mij;
    mij=(a+b)/2;
    while (a!=b)
    {
        if (n<=w[mij])
            b=mij;
        else
        a=mij+1;
    }
    return w[a];
}


int main()
{
    
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    
    int i, j, t, n, k;
    
    for (i=2; i<=NMAX; i++)
    {
        if (!v[i])
            for (j=i; j<=NMAX; j+=i)
                ++v[j];
    }
    for (i=1; i<=NMAX; i++)
    {
        list[ v[i] ][0]++;
        list[ v[i]  ][  list[ v[i] ][0] ]=i;
    }

    scanf("%d", &t);
    for (; t>0; t--)
    {
        scanf("%d %d", &n, &k);
        v[0]=k;
        //tre sa scad complexitatea aici
     //   for (i=n; i>=0; --i)
     //   if (v[i]==k)
     //   {
     //       printf("%d\n", i); 
     //       break;
     //   }
        printf("%d", cauta(list[k], n));
    }
    
    fclose(stdout);
    return 0;
}