#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int a[20], m[20], n;

//【模板】中国剩余定理
// https://www.bilibili.com/video/av25823277
// https://xiaoxiaoh.blog.csdn.net/article/details/103024423

//扩展欧几里得
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

//中国剩余定理
LL CRT() {
    LL ans = 0;
    LL M = 1;
    LL t1, t2;
    for (int i = 1; i <= n; i++) M *= m[i]; //M:所有除数的公倍数,因为是两两互质的，所以，也是最小公倍数

    for (int i = 1; i <= n; i++) {
        LL Mi = M / m[i]; //Mi:把自己除掉后，其它几个除数的乘积
        //求逆元的过程
        //求exgcd(e, m)—>利用欧几里得算法不断递归直到x=1,y=0—>反向递归求出第一层的x和y，x即为e模m的逆元。
        exgcd(Mi, m[i], t1, t2);        //t1就是逆元
        ans = (ans + a[i] * Mi % M * t1) % M; //这个就是套用推导出来的公式了
    }
    return (ans + M) % M; //保证结果为正整数
}

// 快乘模板
// https://www.cnblogs.com/Fy1999/p/8908522.html
LL qmul(LL a, LL b, LL m) {
    LL ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % m;
        a = (a << 1) % m;
        b >>= 1;
    }
    return ans;
}

//中国剩余定理(快乘版本)
LL CRT_QickMul() {
    LL ans = 0;
    LL M = 1;
    LL x, y;
    for (int i = 1; i <= n; i++) M *= m[i];
    for (int i = 1; i <= n; i++) {
        LL Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        x = (x % m[i] + m[i]) % m[i]; //变成最小正整数解,这是为了快乘的特点,转换为最小正整数
        //写一句        //d=(d%MOD+MOD)%MOD; 转化成正数就可以了,网上很多人也是这样做的,尤其在加密解密时。
        ans = (ans + qmul(a[i] * Mi % M, x , M)) % M;
    }
    return (ans + M) % M; //防止为负数
}
int main() {
    //输入+输出重定向
    freopen("../AcWing/N11/China.txt", "r", stdin);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", m + i, a + i); //m是除数,2是余数 ,注意这里数组的数据读入方法,还有下标的开始位置
    }
    printf("%lld\n", CRT());

    printf("%lld\n", CRT_QickMul());
    //关闭文件
    fclose(stdin);
    return 0;
}