#include <iostream>
using namespace std;
void exgcd(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1;
y = 0;
}
else
{
exgcd(b, a % b, y, x);
y -= x * (a / b);
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
int n, B;
cin >> n >> B;
int x, y;
exgcd(B, 9973, x, y);
x *= n;
x = x % 9973;
if (x < 0) x += 9973;
cout << x << endl;
}
return 0;
}
