This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
// 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;
