题目描述

小黄来到了他一直梦寐以求的巧克力工厂，这里有各种各样的巧克力等待品尝。工厂里只有一台巧克力加工机，所有巧克力必须加工完成后才能食用。 巧克力并非一开始就全部加工好，而是会在一天中的不同时间陆续加工完成。不同的巧克力，小黄吃完它所需要的时间也不同。只会吃的小黄完全不懂算法，你能帮他想想办法，让他尽早吃完所有巧克力吗？

输入格式

第一行：一个整数 \(T\)，表示测试用例数量

每组测试用例：

• 第一行：一个整数 \(N\)，表示巧克力数量。
• 接下来 \(N\) 行：每行两个整数 \(s_i,d_i\)：
• \(s_i\)：第 \(i\) 块巧克力的加工完成时间（该时刻及之后才能品尝）。
• \(d_i\)：吃完第 \(i\) 块巧克力所需的时间。

保证 \(1 \le T \le 100\)，\(1 \le N \le 10^5\)，所有测试用例的 \(N\) 之和不超过 \(5\times 10^5\)，\(1 \le s_i,d_i \le 10^9\)。

输出格式

对于每组测试用例，输出一行一个整数，表示小黄吃完所有巧克力的最早时刻。

样例输入

1
3
1 2
3 1
1 1

样例输出

5