题目内容

一条走廊上依次排列着 $n$ 扇自动闸机。第 $i$ 扇闸机按固定周期运行：先连续放行 $a_i$ 秒，再连续关闭 $b_i$ 秒，然后不断重复。所有闸机均从时刻 $0$ 开始进入放行状态。

快递员初始位于第 $1$ 扇闸机前，当前时刻为 $0$。每当他来到一扇闸机前：

• 若该闸机此刻处于放行状态，他立即通过，耗时 $1$ 秒到达下一扇闸机前（或终点）；
• 若该闸机此刻处于关闭状态，他等待至下一次放行开始，再立即通过，同样耗时 $1$ 秒。

通过闸机时，只要求开始通过的那一瞬闸机处于放行状态，不要求整段 $1$ 秒内持续放行。

求他通过全部闸机后到达终点的最早时刻。

约束：测试数据组数不超过 $10^6$。每组数据中闸机数量不超过 $2 \times 10^5$。每扇闸机的放行时长与关闭时长均不超过 $10^9$。单个测试文件中所有闸机数量之和不超过 $10^6$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 10^6$），表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示闸机数量。 接下来 $n$ 行，每行输入两个整数 $a_i, b_i$（$1 \le a_i, b_i \le 10^9$），表示第 $i$ 扇闸机在每个周期中放行和关闭的持续时间。 保证单个测试文件中所有 $n$ 之和不超过 $10^6$。

输出描述

对于每组测试数据，新起一行输出一个整数，表示快递员通过全部闸机后到达终点的最早时刻。

样例1

输入

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

输出

5
6

说明

按题意模拟计算得到。