#include <cstdio>

 #include <cstdlib>

 #include <iostream>

 #include <cstring>

 #define     MOD 9973

 using namespace std;

 typedef long long LL;

 void exgcd(LL a, LL b, LL &d, LL &x, LL&y)

 {

     if( b ==  )

     {

         d = a;

         x = ;

         y = ;

     }

     else

     {

         exgcd(b, a%b, d, x, y);

         int t = x;

         x = y;

         y = t - (a/b)*y;

     }

 }

 int main(int argc, char *argv[])

 {

     int T;

     scanf ( "%d", &T );

     int n, a, b;

     LL d, x, y;

     while( T-- )

     {

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

         a = MOD;

         exgcd(a, b, d, x, y);

         y = (y%MOD)*(n/d)%MOD;

         y = (y+MOD)%MOD;

         cout<<y<<endl;

     }

 }