/**
 * @file 9622.cpp
 * @author Macesuted ([email protected])
 * @date 2024-11-12
 *
 * @copyright Copyright (c) 2024
 *
 */

#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

bool mem1;

typedef __int128_t int128_t;

const int64_t lim = 1e18;

int128_t exgcd(int128_t a, int128_t b, int128_t &x, int128_t &y) {
    if (b == 0) return x = 1, y = 0, a;
    int d = exgcd(b, a % b, y, x);
    return y -= a / b * x, d;
}

void solve(void) {
    int64_t a, b;
    cin >> a >> b;

    int64_t beta1 = 1;
    while (b % 2 == 0) b /= 2, beta1 *= 2;
    while (b % 5 == 0) b /= 5, beta1 *= 5;

    if (b == 1) return cout << "0 1" << endl, void();
    a %= b;

    int ansc = INT_MAX, ansd = 1;
    for (int128_t beta2 = 1; beta2 <= lim; beta2 *= 2)
        for (int128_t beta3 = 1; beta2 * beta3 <= lim; beta3 *= 5) {
            int128_t v = (b - beta2 * beta3 % b * a % b) % b, x, y, g = exgcd(beta1, b, x, y);
            if (v % g) break;
            x = v / g * x % (b / g), y = beta2 * beta3 * b;
            int128_t gg = gcd(x, y);
            x /= gg, y /= gg;
            // cerr << "! " << x << ' ' << y << endl;
            if (ansc > x && y <= int(1e9)) ansc = x, ansd = y;
        }

    cout << ansc << ' ' << ansd << endl;

    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    cin >> _;
    while (_--) solve();

#ifdef LOCAL
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58,
                 from answer.code:10:
/usr/include/c++/13/numeric: In instantiation of ‘constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]’:
answer.code:46:30:   required from here
/usr/include/c++/13/numeric:166:21: error: static assertion failed: std::gcd arguments must be integers
  166 |       static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/13/numeric:166:21: note: ‘std::is_integral_v<__int128>’ evaluates to false
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/type_traits: In instantiation of ‘struct std::make_unsigned<__int128>’:
/usr/include/c++/13/type_traits:1983:11:   required by substitution of ‘template<class _Tp> using std::make_unsigned_t = typename std::make_unsigned::type [with _Tp = __int128]’
/usr/include/c++/13/numeric:173:24:   required from ‘constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]’
answer.code:46:30:   required from here
/usr/include/c++/13/type_traits:1836:62: error: invalid use of incomplete type ‘class std::__make_unsigned_selector<__int128, false, false>’
 1836 |     { typedef typename __make_unsigned_selector<_Tp>::__type type; };
      |                                                              ^~~~
/usr/include/c++/13/type_traits:1744:11: note: declaration of ‘class std::__make_unsigned_selector<__int128, false, false>’
 1744 |     class __make_unsigned_selector;
      |           ^~~~~~~~~~~~~~~~~~~~~~~~