#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } templateT gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);} templateT lcm(T x, T y){ return x == 0 ? 0 : x/gcd(x,y)*y; } vector isprime; vector primes; void sieve(int n){ if((int)isprime.size() >= n+1) return; isprime.assign(n+1, true); isprime[0] = isprime[1] = false; int sqrtn = (int)(sqrt(n * 1.) + .5); for(int i = 2; i <= sqrtn; i ++) if(isprime[i]) { for(int j = i * i; j <= n; j += i) isprime[j] = false; } primes.clear(); for(int i = 2; i <= n; i ++) if(isprime[i]) primes.push_back(i); } typedef int FactorsInt; typedef vector > Factors; void primeFactors(FactorsInt x, Factors &out_v) { out_v.clear(); int sqrtx = (int)(sqrt(x*1.) + 10.5); sieve(sqrtx); for(vector::const_iterator p = primes.begin(); p != primes.end(); ++ p) { if(*p > sqrtx) break; if(x % *p == 0) { int t = 1; x /= *p; while(x % *p == 0) { t ++; x /= *p; } out_v.push_back(make_pair(*p, t)); } } if(x != 1) out_v.push_back(make_pair(x, 1)); } long long inverse(signed long long a, const long long MOD) { a %= MOD; if(a < 0) a += MOD; signed long long b = MOD, u = 1, v = 0; while(b) { signed long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if(u < 0) u += MOD; return u; } ll crt(ll a1, ll a2, ll n1, ll n2) { ll b = n1 % n2; ll t = inverse(b, n2); ll h = ((a2 - a1) * t % n2 + n2) % n2; return a1 + n1 * h; } int powpq(int p, int q) { int r = 1; rep(i, q) r *= p; return r; } int main() { sieve(31623); int N; scanf("%d", &N); Factors fs; map mods; bool ok = true; rep(i, N) { int X, Y; cin >> X >> Y; primeFactors(Y, fs); each(j, fs) { int p = j->first, q = j->second; int pq = powpq(p, q); pii &t = mods[p]; int u = min(pq, powpq(p, t.first)); ok &= t.second % u == X % u; if(t.first < q) { t.first = q; t.second = X % pq; } } } if(!ok) { puts("-1"); return 0; } ll a = 0, n = 1; each(i, mods) { int p = i->first, q = i->second.first, x = i->second.second; int pq = powpq(p, q); a = crt(a, x, n, pq); n *= pq; } if(a == 0) a += n; printf("%lld\n", a); return 0; }