#include <bits/stdc++.h>

 using namespace std;

 int gcd(int x,int y)

 {

     return y==?x:gcd(y,x%y);

 }

 int main()

 {

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         while(n--)

         {

             int a,b;

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

             for(int i=b;;i++)

             {

                 if(gcd(i,a)==b&&i!=b&&gcd(i,b)==b)

                 {

                     printf("%d\n",i);

                     break;

                 }

             }

         }

     }

     return ;

 }