CF1501A Alexey and Train

Alexey坐上了一趟火车。假设火车从0这个时刻出发，经过 $n$ 个车站。车站的编号为 1至 $n$ 。火车会在第 $a_i$ 的时刻到达第 $i$ 个站，并在第 $b_i$ 的时刻离开。 由于天气原因，火车从第 $i-1$ 个站到第 $i$ 个站会比原定时间多走 $tm_i$ 的时间（如果 $i$ 为1，那么 $b_0$ 就是火车从始发站离开的时间，并且 $b_0$ 等于0）。 如果满足以下2个条件，火车将会从第 $i$ 个站离开： 1. 在车站至少停留 $\lceil \dfrac{b_i-a_i}{2} \rceil$ 个时刻（向上取整）。 2. 当前时刻 $\ge b_i$ 。 请帮Alexey求出到达第 $n$ 个站所花费的时间。

第一行输入一个整数 $t$ （ $1 \le t \le 100$ ），表示数据组数。 对于每一组测试数据，第一行输入一个整数 $n$ （ $1 \le n \le 100$ ），表示车站的数量。 第二行起的 $n$ 行，每行两个整数 $a_i,b_i$ （ $1 \le a_i < b_i \le 10^6 $ ）。保证 $a_i

对于每个测试数据，输出一个整数，表示 Alexey火车到达第 $n$ 个车站所需的时间。

In the first test case, Alexey arrives at station $ 1 $ without any delay at the moment $ a_1 = 2 $ (since $ tm_1 = 0 $ ). After that, he departs at moment $ b_1 = 4 $ . Finally, he arrives at station $ 2 $ with $ tm_2 = 2 $ extra time, or at the moment $ 12 $ . In the second test case, Alexey arrives at the first station with $ tm_1 = 1 $ extra time, or at moment $ 2 $ . The train, from one side, should stay at the station at least $ \left\lceil \frac{b_1 - a_1}{2} \right\rceil = 2 $ units of time and from the other side should depart not earlier than at moment $ b_1 = 4 $ . As a result, the trains departs right at the moment $ 4 $ . Using the same logic, we can figure out that the train arrives at the second station at the moment $ 9 $ and departs at the moment $ 10 $ ; at the third station: arrives at $ 14 $ and departs at $ 15 $ ; at the fourth: arrives at $ 22 $ and departs at $ 23 $ . And, finally, arrives at the fifth station at $ 32 $ .