Elina正在读刘汝佳写的一本书，是关于一种非负整数的表示方法，如下所示：
选择k个不同的正整数a1，a2，…，ak，对于某个整数m分别对ai（1≤i≤k）作模运算得余数ri，如果适当选择a1，a2，…，ak，则整数m可由整数对（ai，ri）唯一确定。
“根据m计算整数对，是太容易了”，Elina说，“但是如何根据整数对来计算m呢？”
Elina正在读刘汝佳写的一本书，是关于一种非负整数的表示方法，如下所示：
选择k个不同的正整数a1，a2，…，ak，对于某个整数m分别对ai（1≤i≤k）作模运算得余数ri，如果适当选择a1，a2，…，ak，则整数m可由整数对（ai，ri）唯一确定。
“根据m计算整数对，是太容易了”，Elina说，“但是如何根据整数对来计算m呢？”
输入有多组测试例，每个测试例有多行。
第一行是一个整数k。
第2～k＋1行，是一对整数（ai，ri）（1≤i≤k）。
对每个测试例输出一行，是非负整数m。如果有多个m，则输出最小的一个。若无解，输出—1。
2 8 7 11 9
31
输入和输出的所有整数，都是非负整数，而且是64位。