1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn = 1000000;
 8 bool flag[maxn+5];
 9 int prim[80000];
10 int dabiao()
11 {
12     memset(flag,0,sizeof(flag));
13     for(int i = 4;i <= maxn;i += 2)
14     flag[i] = 1;
15     for(int i = 2;i <= sqrt((double)maxn);++i)
16     if(!flag[i])
17     {
18         for(int j = i * i;j <= maxn;j += i)
19         flag[j] = 1;
20     }
21     int tot = 0;
22     for(int i = 2;i <= maxn;++i)   //&acute;&Oacute;2&iquest;&ordf;&Ecirc;&frac14;&pound;&not;&ordm;&ouml;&Acirc;&Ocirc;&Aacute;&Euml;1 
23     if(!flag[i])
24     prim[tot++] = i;
25     return tot;
26 }
27     
28 int main()
29 {
30     int T,a,b,c;
31     int f = dabiao();
32     scanf("%d",&T);
33     while(T--)
34     {
35         scanf("%d%d",&a,&b);
36         a /= b;
37         for(int i = 0;i < f;++i)
38         if(a % prim[i] != 0)
39         {
40             printf("%d\n",prim[i] * b);
41             break;
42         }
43     }
44     return 0;
45 }