#if defined(local)
#include "./noya/debug.hpp"
#else
#define debug(...) 42
#endif

#include "bits/stdc++.h"

using namespace std;
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define pb emplace_back
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}


#include <cstdint>
using ll = int64_t;
using ull = uint64_t;
namespace noya {
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = 1010000000;
template <> constexpr ll infty<ll> = 2020000000000000000;
template <> constexpr unsigned infty<unsigned> = infty<int>;
template <>
constexpr ull infty<ull> = infty<ll>;
template <>
constexpr __int128 infty<__int128> =
    __int128(infty<ll>) * 2000000000000000000;
template <> constexpr double infty<double> = infty<ll>;
template <> constexpr long double infty<long double> = infty<ll>;
} // namespace noya


using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
const int INF = 1010000000;
const ll LNF = 1010000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

namespace noya {}



#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

// https://github.com/the-tourist/algo/blob/master/numeric/extgcd.cpp
template <typename T> T extgcd(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T p = b / a;
  T g = extgcd(b - p * a, a, y, x);
  x -= p * y;
  return g;
}

template <typename T> bool diophantine(T a, T b, T c, T &x, T &y, T &g) {
  if (a == 0 && b == 0) {
    if (c == 0) {
      x = y = g = 0;
      return true;
    }
    return false;
  }
  if (a == 0) {
    if (c % b == 0) {
      x = 0;
      y = c / b;
      g = abs(b);
      return true;
    }
    return false;
  }
  if (b == 0) {
    if (c % a == 0) {
      x = c / a;
      y = 0;
      g = abs(a);
      return true;
    }
    return false;
  }
  g = extgcd(a, b, x, y);
  if (c % g != 0) {
    return false;
  }
  T dx = c / a;
  c -= dx * a;
  T dy = c / b;
  c -= dy * b;
  x = dx + (T)((__int128)x * (c / g) % b);
  y = dy + (T)((__int128)y * (c / g) % a);
  g = abs(g);
  return true;
  // |x|, |y| <= max(|a|, |b|, |c|) [tested]
}

bool crt(long long k1, long long m1, long long k2, long long m2, long long &k,
         long long &m) {
  k1 %= m1;
  if (k1 < 0)
    k1 += m1;
  k2 %= m2;
  if (k2 < 0)
    k2 += m2;
  long long x, y, g;
  if (!diophantine(m1, -m2, k2 - k1, x, y, g)) {
    return false;
  }
  long long dx = m2 / g;
  long long delta = x / dx - (x % dx < 0);
  k = m1 * (x - dx * delta) + k1;
  m = m1 / g * m2;
  assert(0 <= k && k < m);
  return true;
}

// for distinct prime modulos
template <typename T>
void crt_garner(const std::vector<int> &p, const std::vector<int> &a, T &res) {
  assert(p.size() == a.size());
  auto inverse = [&](int q, int m) {
    q %= m;
    if (q < 0)
      q += m;
    int b = m, u = 0, v = 1;
    while (q) {
      int t = b / q;
      b -= t * q;
      std::swap(q, b);
      u -= t * v;
      std::swap(u, v);
    }
    assert(b == 1);
    if (u < 0)
      u += m;
    return u;
  };
  std::vector<int> x(p.size());
  for (int i = 0; i < (int)p.size(); i++) {
    assert(0 <= a[i] && a[i] < p[i]);
    x[i] = a[i];
    for (int j = 0; j < i; j++) {
      x[i] = (int)((long long)(x[i] - x[j]) * inverse(p[j], p[i]) % p[i]);
      if (x[i] < 0)
        x[i] += p[i];
    }
  }
  res = 0;
  for (int i = (int)p.size() - 1; i >= 0; i--) {
    res = res * p[i] + x[i];
  }
}

const ll L = 1e9;

void solve() {
  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) {
    cout << "0 1\n";
    return;
  }
  a %= b;

  int ansc = L, ansd = L;
  for (int64_t beta2 = 1; beta2 * b <= L; beta2 *= 2)
    for (int64_t beta3 = 1; beta2 * beta3 * b <= L; beta3 *= 5) {
      int64_t v = (b - beta2 * beta3 % b * a % b) % b, x, y;
      extgcd(beta1, b, x, y);
      x = (v * x % b + b) % b, y = beta2 * beta3 * b;
      int64_t gg = gcd(x, y);
      x /= gg, y /= gg;
      if (ansc > x)
        ansc = x, ansd = y;
    }

  cout << ansc << ' ' << ansd << "\n";
  return;
}

int main() {
  int T;
  cin >> T;
  while (T--)
    solve();
}