该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

传送门

题目描述

Y 同学需要依次穿过 $n$ 个传送门，传送门按照 $1,2,\dots,n$ 的顺序排列。

第 $i$ 个传送门具有固定的运行周期：

所有传送门均从时刻 $0$ 开始进入开启状态。

对于任意非负整数时刻 $t$ ，设

r=t\bmod(a_i+b_i)

当 $0\le r<a_i$ 时，第 $i$ 个传送门处于开启状态；否则处于关闭状态。

Y 同学初始位于第 $1$ 个传送门前，当前时刻为 $0$ 。当他到达第 $i$ 个传送门前时：

Y 同学必须按照编号从小到大的顺序依次穿过所有传送门。

请你求出 Y 同学穿过全部传送门并到达终点的最早时刻。

第一行包含一个整数 $T$ ，表示测试数据组数。

对于每组测试数据：

第一行包含一个整数 $n$ ，表示传送门数量。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$ ，分别表示第 $i$ 个传送门每个周期中开启和关闭的持续时间。

对于每组测试数据，输出一行一个整数，表示 Y 同学穿过所有传送门后到达终点的最早时刻。

5
6

对于 $100\%$ 的数据，保证：

测试点编号	分值	具体限制	特殊性质
$1\sim2$	$10$	$\sum n\le 100$ ， $a_i,b_i\le 100$	特殊性质 A
$3\sim4$		$\sum n\le 10^4$	特殊性质 B
$5\sim6$		$\sum n\le 10^5$	特殊性质 C
$7\sim10$	$20$	$\sum n\le 10^4$ ， $a_i,b_i\le 10^4$	无
$11\sim14$	$20$	$\sum n\le 2\times 10^5$
$15\sim20$	$30$	$\sum n\le 10^6$