#CF2266F. MEX Replacement

MEX Replacement

Problem Description

You are given a multiset of non-negative integers in compressed form. That is, for each value $x_i$ in the multiset, you know the number of its occurrences $y_i$.

In one operation, you may choose any non-empty collection of elements currently in the multiset, remove all chosen elements, and insert one element equal to their $\operatorname{MEX}$$^{\text{∗}}$.

You may perform the operation any number of times, possibly zero.

Find the maximum integer that can appear in the multiset at any moment.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1,c_2,\ldots,c_k$ is the smallest non-negative integer $x$ that does not occur in the collection.

Input Format

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of distinct integers in the initial multiset.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i \le 10^9$, $1 \le y_i \le 10^9$), indicating that the integer $x_i$ occurs exactly $y_i$ times in the initial multiset.

The integers $x_1,x_2,\ldots,x_n$ are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output Format

For each test case, output one integer — the maximum integer that can appear in the multiset at any moment.

Examples

10
4
2 2
0 3
4 1
1 2
1
10 1
1
2 3
3
0 1
2 2
3 1
3
0 4
1 2
2 1
1
0 100
2
2 7
3 1
2
0 1
3 3
3
0 1
1 1
59 1
4
0 5
1 1
2 3
3 1
5
10
3
4
4
7
4
3
59
5

Note

In the first test case, the initial multiset is $\{0,0,0,1,1,2,2,4\}$.

We can replace $\{0,1,2\}$ with $3$, obtaining $\{0,0,1,2,3,4\}$. Then, we can replace $\{0,1,2,3,4\}$ with $5$.

It can be shown that no integer greater than $5$ can appear, so the answer is $5$.

In the second test case, $10$ already appears in the initial multiset, and no greater integer can appear. Thus, the answer is $10$.

Source

Imported from Codeforces — Codeforces Round 1122 (Div. 3).