题目内容

Tk 要依次穿过 $n$ 个传送门。第 $i$ 个传送门有自己的开关周期，它会连续开启 $a_i$ 秒，然后连续关闭 $b_i$ 秒，之后不断重复。

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

Tk 初始位于第 $1$ 个传送门前，时间为 $0$。当他来到一个传送门前时：

• 如果该传送门此刻处于开启状态，他会立刻通过，耗时 $1$ 秒到达下一个传送门前；
• 如果该传送门此刻处于关闭状态，他会等待到它下一次开启，然后立刻通过，同样耗时 $1$ 秒。

请你求出 Tk 穿过所有传送门后，到达终点的最早时刻。

输入描述

每个测试文件内包含多组测试数据。

第一行输入一个整数 $T$（$1\leq T\leq 10^6$），代表测试数据的组数。

对于每组测试数据：

第一行输入一个整数 $n$（$1\leq n\leq 2\times 10^5$），表示传送门的数量。

接下来 $n$ 行，每行输入两个整数 $a_i,b_i$（$1\leq a_i,b_i\leq 10^9$），表示第 $i$ 个传送门在每个周期中开启和关闭的持续时间。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $10^6$。

输出描述

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

样例1

输入

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

输出

5
6