传送门

题目描述

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

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

• 连续开启 $a_i$ 秒；
• 随后连续关闭 $b_i$ 秒；
• 此后按照相同规律不断重复。

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

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

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

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

• 若传送门处于开启状态，他会立即通过；
• 若传送门处于关闭状态，他会等待至该传送门下一次开启，再立即通过；
• 通过一个传送门需要 $1$ 秒。

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

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

输入格式

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

对于每组测试数据：

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

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

输出格式

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

样例

样例输入 #1

2
3
1 1
1 1
1 1
4
2 3
1 2
3 1
2 2

样例输出 #1

5
6

数据范围与约定

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

• $1\le T\le 10^6$；
• $1\le n\le 2\times 10^5$；
• $1\le a_i,b_i\le 10^9$；
• 单个测试文件中所有测试数据的 $n$ 之和不超过 $10^6$。

• 特殊性质 A：保证所有传送门均满足 $a_i=b_i=1$。
• 特殊性质 B：保证所有传送门均满足 $b_i=1$。
• 特殊性质 C：保证 Y 同学到达每个传送门时，该传送门均处于开启状态。