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

// 拡張ユークリッドの互除法
ll extGcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = extGcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}

int main() {
  int T;
  cin >> T;
  const ll MOD = 1'000'000'000;

  while (T--) {
    ll N, M;
    cin >> N >> M;

    ll g = gcd(N, MOD);
    if (M % g != 0) {
      cout << -1 << endl;
      continue;
    }

    // N / g, M / g, MOD / g にスケールダウン
    N /= g;
    M /= g;
    ll mod_g = MOD / g;

    // N * k ≡ -M (mod MOD) を解く
    // N * k ≡ -M (mod mod_g) に変形

    ll x, y;
    extGcd(N, mod_g, x, y); // x が N の逆元
    x = (x % mod_g + mod_g) % mod_g; // 正にする

    ll k = (-M % mod_g + mod_g) % mod_g;
    k = (k * x) % mod_g;

    // k を g 倍して元に戻す
    cout << k * g << endl;
  }

  return 0;
}