M. The Maximum MEX Challenge
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this round of the Squid Game, the players are presented with $$$n$$$ locked vaults, each containing a hidden number. The guards provide an interval $$$[l, r]$$$ for each vault, indicating that the number inside must be chosen from this range.

Each player must select exactly one number from each interval, forming a sequence of $$$n$$$ numbers. The objective is to maximize the MEX of this sequence.

The mex of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:

  • The mex of $$$[0, 1, 2]$$$ is $$$3$$$.
  • The mex of $$$[1, 2, 3]$$$ is $$$0$$$.
  • The mex of $$$[0, 2, 3]$$$ is $$$1$$$.
Given $$$n$$$ intervals of the form $$$[l_i, r_i]$$$, choose one integer from each interval such that the resulting sequence has the maximum possible MEX.
Input
  • The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the number of intervals.
    • The next $$$n$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i \leq r_i \leq n$$$), representing the $$$i$$$-th interval $$$[l_i, r_i]$$$.
It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$10^6.$$$
Output

Print a single integer, the maximum possible mex of the sequence obtained by selecting one integer from each interval.

Example
Input
3
1
0 0
4
0 1
0 3
1 2
0 0
3
0 1
0 0
3 3
Output
1
4
2