1 //Accepted    228 KB    0 ms
 2 #include <cstdio>
 3 #include <cstring>
 4 int gcd(int a,int b)
 5 {
 6     if (b==0) return a;
 7     return gcd(b,a%b);
 8 }
 9 int a,b,c;
10 void slove()
11 {
12     for (c=1;;c++)
13     {
14         if (c!=b && gcd(a,c)==b)
15         break;
16     }
17     printf("%d\n",c);
18 }
19 int main()
20 {
21     int T;
22     scanf("%d",&T);
23     while (T--)
24     {
25         scanf("%d%d",&a,&b);
26         slove();
27     }
28     return 0;
29 }