题目描述

求满足x≡ai (mod mi)的最小非负整数x，可能无解。模数不要求互质。

本题为一本通1635的本地训练修订版。

输入

读至EOF，1..10组，每组n后跟n行mi ai；1≤n≤10^5，所有组n之和≤10^5，1≤mi≤10^9，0≤ai<mi。保证每组所有mi的最小公倍数不超过10^18。

输出

每组有解输出最小非负解，否则-1。

输入样例

2
8 7
11 9

输出样例

31

修订说明

统一源描述最小正与输出非负冲突为最小非负；明确最终周期≤10^18及mi上界以保64位输出，n上界保留。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：统一源描述最小正与输出非负冲突为最小非负；明确最终周期≤10^18及mi上界以保64位输出，n上界保留。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1635。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。