#pragma region Modefs #define retword "-1" constexpr long long MAXCOMB = 202020; constexpr long long MOD = 1000000007; constexpr long double EPS = 1e-9; #pragma endregion //--MACROS--------------------------------- #pragma region Macros #include #define SORT(x) sort((x).begin(), (x).end()) #define RSORT(x) sort((x).rbegin(), (x).rend()) #define ALL(x) (x).begin(), (x).end() #define REV(x) reverse(ALL(x)) #define rep(i, n) for (ll i = 0; i < n; i++) #define reps(i, m, n) for (ll i = m; i < n; i++) #define repr(i, m, n) for (ll i = m; i >= n; i--) #define SP << " " << #define lwb(x,n) distance(x.begin(),lower_bound(ALL(x),(n))) #define upb(x,n) distance(x.begin(),upper_bound(ALL(x),(n))) #define fora(i, ...) if(ll i = -1) for(__VA_ARGS__) if(i++, true) #ifdef _MY_DEBUG #define isdebug true #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0,a1,a2,a3,x,...) x #define debug_1(x1) cout<<#x1<<": "<; using TP = tuple; ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; } ll overmul(ll a, ll b){ return (b?(a>INF2/b?INF2:a*b):0LL);} template using v = vector; template using vv = vector>; template using vvv = vector>>; template bool maxi(T &a, const T &b){ if(a bool mini(T &a, const T &b){ if(b T sumer(const vector& a){ return accumulate(ALL(a),(T)0); } template T miner(const vector& a){ return *min_element(ALL(a)); } template T maxer(const vector& a){ return *max_element(ALL(a)); } template T ceil(T a, T b) { return a/b + !!(a%b); } template ll bs(ll ok, ll ng, T checker){ while( abs(ok-ng)>1 ){ ll mid = (ok+ng)/2; (checker(mid)?ok:ng) = mid; } return ok; } template ld bs2(ld ok, ld ng, T checker){ rep(i,180){ ld mid = (ok+ng)/2; (checker(mid)?ok:ng) = mid; } return ok; } template ll UNIQ(vector &a){ SORT(a);a.erase(unique(ALL(a)),a.end()); return a.size();} template ostream &operator<<(ostream &os, const pair &pe) { os << pe.first << " " << pe.second; return os;} template ostream &operator<<(ostream &os, const v &ve) { rep(i,ve.size()) os<< (i?" ":"")< struct ModInt { ll x; ModInt() : x(0) {} ModInt(ll y) : x(y >= 0 ? ( y= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int) (1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inv(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } bool operator<(const ModInt &p) const {return x < p.x; } ModInt operator+(const ll &q) const {return ModInt(*this) += (ModInt)q; } ModInt operator-(const ll &q) const {return ModInt(*this) -= (ModInt)q; } ModInt operator*(const ll &q) const {return ModInt(*this) *= (ModInt)q; } ModInt operator/(const ll &q) const {return ModInt(*this) /= (ModInt)q; } bool operator==(const ll &q) const {return x == q; } bool operator!=(const ll &q) const {return x != q; } ModInt operator++(){ if(++x == mod) x = 0; return *this; } ModInt operator--(){ x = (x == 0 ? mod-1 : x-1); return *this; } ModInt operator++(int){ const ModInt res(*this); ++*this; return res; } ModInt operator--(int){ const ModInt res(*this); --*this; return res; } ModInt inv() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(ll n, bool inv=false) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } if(inv) ret=ret.inv(); return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { ll t; is >> t; a = ModInt< mod >(t); return (is); } }; using mint = ModInt< MOD >; mint mpow(ll x, ll n, bool inv=false) { mint ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } if(inv) ret=ret.inv(); return ret; } mint fac[MAXCOMB], finv[MAXCOMB], inv[MAXCOMB]; void cinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; reps(i, 2, MAXCOMB){ fac[i] = fac[i - 1] * i; inv[i] = inv[MOD%i] * -(MOD/i); finv[i] = finv[i - 1] * inv[i]; } } mint cmb(int n, int k){ // 二項係数計算 if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * finv[k] * finv[n-k]; } #pragma endregion //--GLOBAL--------------------------------- // mが互いに素でない場合に前処理する。 // modのgcd部分(素因子の共通部分)をとって、指数の大きかったほうの情報量が真に大きいので、そちら側のみ残す。 ll PreGarner(vector &b, vector &m, ll mod) { ll res = 1; rep(i,b.size()) { rep(j,i) { ll g = gcd(m[i], m[j]); // 素因子の共通部分 if ((b[i] - b[j]) % g != 0) return -1; // no solution // mを共通でない部分にする m[i] /= g; m[j] /= g; // 共通部分 g は、指数の大きい方に振り分ける // m[i] がまだもってる因子の1つ以上を gi, ほかは gj に。 ll gi = gcd(m[i], g), gj = g/gi; // iに行くべき gj の因子はgcdで判定できる。これをgiに移す。 do { g = gcd(gi, gj); gi *= g, gj /= g; } while (g != 1); m[i] *= gi, m[j] *= gj; // i 側と j 側に戻す // 余り b を再計算 b[i] %= m[i], b[j] %= m[j]; } } for (int i = 0; i < (int)b.size(); ++i) (res *= m[i]) %= mod; return res; // lcm % mod を返す } // 負の数にも対応した mod (a = -11 とかでも OK) inline ll getmod(ll a, ll m) { ll res = a % m; if (res < 0) res += m; return res; } // 拡張 Euclid の互除法 ll extGCD(ll a, ll b, ll &p, ll &q) { if (b == 0) { p = 1; q = 0; return a; } ll d = extGCD(b, a%b, q, p); q -= a/b * p; return d; } // 逆元計算 (ここでは a と m が互いに素であることが必要) ll modinv(ll a, ll m) { ll x, y; extGCD(a, m, x, y); return getmod(x, m); // 気持ち的には x % m だが、x が負かもしれないので } // Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない) // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (getmod. m[k])" // coeffs[k] = m[0]m[1]...m[k-1] // constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2] ll Garner(vector b, vector m, ll mod) { m.push_back(mod); // sentinel vector coeffs((int)m.size(), 1); vector constants((int)m.size(), 0); for (int k = 0; k < (int)b.size(); ++k) { ll t = getmod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]); for (int i = k+1; i < (int)m.size(); ++i) { (constants[i] += t * coeffs[i]) %= m[i]; (coeffs[i] *= m[k]) %= m[i]; } } return constants.back(); } //--MAIN----------------------------------- void Main() { ll N; cin>>N; v<> A(N),B(N); rep(i,N) cin>>A[i]>>B[i]; bool all0=all_of(ALL(A),[](ll x){return x==0;}); ll x=PreGarner(A,B,MOD); if(all0) cout<< x <<"\n"; else if(x==-1) cout<< -1 <<"\n"; else cout<< Garner(A,B,MOD) <<"\n"; } //--START---------------------------------- int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); // ifstream in("input.txt"); cin.rdbuf(in.rdbuf()); // ofstream out("output.txt"); cout.rdbuf(out.rdbuf()); cout << fixed << setprecision(15); // ll Qkai; cin>>Qkai; rep(QQ,Qkai) Main(); Main(); } //-----------------------------------------