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。