本题没有可用的提交语言。

描述

在实时调度中，可预测性非常重要，也就是说，在真正运行任务之前，我们希望了解整个调度安排。速率单调调度在周期性任务的实时调度中非常流行，在这种调度方式下，周期较短的任务具有更高的优先级。然而，要确定每个任务的开始时间和结束时间仍然很困难，并且在每个周期中这些时间可能会有所不同，尤其是对于优先级较低（即周期较长）的任务。超周期，即所有任务周期的最小公倍数，通常太大，以至于在实际描述整个调度安排时不太实用。不过，如果任务周期是调和的（即一个周期是另一个周期的倍数），就有可能快速找到每个任务的开始时间和结束时间，因为此时的调度会变得更加规律。

图 1 展示了周期性任务$T_1$、$T_2$、$T_3$、$T_4$，它们的执行时间分别为$1$、$1$、$3$、$1$，周期分别为$2$、$4$、$16$、$32$。使用速率单调调度算法，这些任务是可调度的，每个任务都在其周期内完成执行，因为$T_1$、$T_2$、$T_3$、$T_4$分别在时间$1$、$2$、$12$、$16$完成执行。$T_3$在时间$4$和时间$8$被$T_1$和$T_2$抢占，并在时间$7$和时间$11$恢复执行。

输入

所有输入的数字都是正整数，小于$500000$，用空格或换行符分隔。第一行是任务集的数量。然后，任务集按顺序列出。每个任务集首先是一行表示任务数量（不超过$100$）的数字，接着是若干行任务执行时间和周期的数对，且执行时间小于周期。这些周期是调和的（一个是另一个的倍数），未排序，并且在一个任务集中各不相同。

输出

对于每个任务集，如果使用速率单调调度算法可调度，找出并输出具有最大周期的任务的完成时间；否则输出$-1$。

输入数据 1

3
4
1 2
1 4
3 16
1 32
3
1 4
4 8
256 1024
3
1 2
3 8
1 4

输出数据 1

16
1024
-1

来源

2003 年亚洲高雄竞赛