504038 - 扩展中国剩余定理

【题目描述】扩展中国剩余定理(ExCRT)

给定n组非负整数ai和ni,求解关于x的方程组的最小非负整数解。 {█(x≡a_1 (mod n_1)@x≡a_2 (mod n_2 )@…@x≡a_n (mod n_n))┤

输入

输入第一行包含整数T(1≤T≤10^5)。 接下来n行,每行两个非负整数ni,ai(1≤ai,ni≤10^12,保证所有ai的最小公倍数不超过1018)。

输出

输出一行,为满足条件的最小非负整数x。

样例

输入

3
11 6
25 9
33 17

输出

  809
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题