1 #include <bits/stdc++.h>
 2 using namespace std ; 
 3  
 4 const int mod = 9973 ; 
 5 int T,n,A,B,inv,x,y,t ; 
 6 
 7 inline int read() 
 8 {
 9     int x = 0 , f = 1 ; 
10     char ch = getchar() ; 
11     while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f = -1 ; ch = getchar() ; } 
12     while(ch>=‘0‘&&ch<=‘9‘) { x = x * 10+ch-48 ; ch = getchar() ; } 
13     return x * f ; 
14 }
15 
16 inline int gcd(int a,int b) 
17 {
18     if(!b) {
19         x = 1 ,y = 0 ; 
20         return a ; 
21     }
22     int tmp = gcd(b,a%b) ; 
23     t = x ; 
24     x = y ; 
25     y = t - a/b*y ; 
26     return tmp ; 
27 }
28 
29 int main() 
30 {
31     T = read() ;  
32     while(T--) 
33     {
34         A = read() ; B = read() ; 
35         gcd(B,mod) ; 
36         x = ( x%mod + mod )%mod ;     //  其实每次 加的是 mod /gcd(B,mod)   但是 因为 两者互质  
37         printf("%d\n",A*x%mod) ; 
38     }
39     return 0 ; 
40 }