void Extend_Gcd(LL a, LL b, LL &g, LL &x, LL &y)
{
    if (!b) g = a, x = 1, y = 0;
    else { Extend_Gcd(b, a%b, g, y, x); y -= x * (a/b); }
}
 
LL inv(LL a, LL n)
{
    LL d, x, y;
    Extend_Gcd(a, n, d, x, y);
    return d == 1 ? (x+n)%n : -1;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        LL a, b;
        cin >> a >> b;
        cout << (a*inv(b, 9973)) % 9973 << endl;
    }
    return 0;
}