// https://vjudge.csgrandeur.cn/problem/HDU-1576
#include <bits/stdc++.h>
typedef long long LL;
/*
测试用例
2
1000 53
87 123456789

答案
7922
6060
*/
using namespace std;
const int MOD = 9973;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        LL x, y;
        LL a, b;
        cin >> a >> b;
        exgcd(b, MOD, x, y);
        x = (x % MOD + MOD) % MOD; //对比使用费马小定理，这里对于扩展欧几里得算出的逆元，还需要进一步模一下 MOD才行，否则可能是负的
        cout << (x * a) % MOD << endl;
    }
    return 0;
}