#include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = ;

 bool flag[maxn+];

 int prim[];

 int dabiao()

 {

     memset(flag,,sizeof(flag));

     for(int i = ;i <= maxn;i += )

     flag[i] = ;

     for(int i = ;i <= sqrt((double)maxn);++i)

     if(!flag[i])

     {

         for(int j = i * i;j <= maxn;j += i)

         flag[j] = ;

     }

     int tot = ;

     for(int i = ;i <= maxn;++i)   //&acute;&Oacute;2&iquest;&ordf;&Ecirc;&frac14;&pound;&not;&ordm;&ouml;&Acirc;&Ocirc;&Aacute;&Euml;1

     if(!flag[i])

     prim[tot++] = i;

     return tot;

 }

 int main()

 {

     int T,a,b,c;

     int f = dabiao();

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&a,&b);

         a /= b;

         for(int i = ;i < f;++i)

         if(a % prim[i] != )

         {

             printf("%d\n",prim[i] * b);

             break;

         }

     }

     return ;

 }