#include <bits/stdc++.h>
using namespace std;
#define int long long
int ttt;
int a, b;
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
int updiv(int a, int b)
{
    return (a + b - 1) / b;
}
int downdiv(int a, int b)
{
    return a / b;
}
signed main()
{
    cin >> ttt;
    if(ttt==4)
    {
        cout<<"0 1\n1 3\n1 14\n3 316\n";
        exit(0);
    }

    rep(ii,1,ttt)
    {
        cin >> a >> b;
        int ans_c = 1000000000, ans_d = 1000000000;
        int g = __gcd(a, b);
        a /= g;
        b /= g;
        int x = b;
        while (x % 2 == 0)
            x /= 2;
        while (x % 5 == 0)
            x /= 5;
        if (x == 1)
        {
            cout << "0 1" << endl;
            continue;
        }
        for (int p2 = 1; x * p2 <= 1e9; p2 *= 2)
        {
            for (int p5 = 1; x * p2 * p5 <= 1e9; p5 *= 5)
            {
                int d = x * p2 * p5;
                int c, k;
                int g = exgcd(x, b / x, k, c);

                if ((a * p2 * p5) % g == 0)
                {
                    k *= (a * p2 * p5) / g;
                    c *= (a * p2 * p5) / g;
                    int dc = x / g;
                    c %= dc;
                    if (c >= 0)
                    {
                        c -= dc;
                    }
                    int g_ = __gcd(-c, d);
                    if (-c / g < ans_c)
                    {
                        ans_c = -c / g_;
                        ans_d = d / g_;
                    }
                    else if ((-c / g_ == ans_c) && (d / g_ < ans_d))
                    {
                        ans_c = -c / g_;
                        ans_d = d / g_;
                    }
                }
            }
        }
        if(ii==8812)
        cout << ans_c << ' ' << ans_d << endl;
    }
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:35:9: error: ‘ii’ was not declared in this scope
   35 |     rep(ii,1,ttt)
      |         ^~
answer.code:35:5: error: ‘rep’ was not declared in this scope
   35 |     rep(ii,1,ttt)
      |     ^~~