Problem Description

银狼既然是骇客，为什么不直接tp过去呢？

银狼正在执行一次网络渗透任务。她从网络表层出发，需要沿深度方向依次通过 $n$ 个漏洞注入点，抵达核心数据库。网络表层的深度为 $0$。

每深入一层消耗 $1$ 点以太能量。第 $i$ 个注入点位于深度 $x_i$ 处，经过时银狼可以发动以太编辑，恢复 $a_i$ 点能量。若以太能量低于 $0$ 及以下，那么银狼的任务就失败了。

请你计算最小的初始以太能量 $X$，使得她顺利完成任务，依次经过所有注入点。

Input Format

第一行一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。保证 $\sum n \le 2 \times 10^5$。

每组数据：第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示注入点数量。接下来 $n$ 行，每行两个整数 $x_i, a_i$（$1 \le x_i, a_i \le 10^{12}$），表示第 $i$ 个注入点的深度和可恢复能量。保证 $x_i$ 严格递增。

Output Format

对于每组数据，输出一行一个整数，表示最小的初始以太能量 $X$。

2
3
2 3
5 1
7 2
1
10 5

3
10

Hint

第一组数据：初始能量 $X = 3$。走到深度 $2$ 时剩余 $1$，注入恢复 $3$ 后变为 $4$；走到深度 $5$ 时剩余 $2$，注入恢复 $1$ 后变为 $3$；走到深度 $7$ 时剩余 $1$，注入恢复 $2$ 后变为 $3$。全程能量未耗尽。可证 $X < 3$ 无法通过。

第二组数据：仅一个注入点，需要至少 $10$ 点能量走到深度 $10$。