F. Minimize the Graph
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. The graph is constructed as follows: for each vertex $$$i$$$ from $$$2$$$ to $$$n$$$, you are given two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \lt i$$$). For each integer $$$j \in [l_i, r_i]$$$, the graph contains a directed edge from $$$j$$$ to $$$i$$$. There are no other edges in the graph.

Consider a second directed graph on the same $$$n$$$ vertices. For any two distinct vertices $$$x$$$ and $$$y$$$, a path from $$$x$$$ to $$$y$$$ must exist in the second graph if and only if it exists in the first graph.

Find the minimum possible number of edges in the second graph.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of vertices.

The next $$$n-1$$$ lines describe the edges of the graph. The $$$i$$$-th of these lines contains two integers $$$l_{i+1}$$$ and $$$r_{i+1}$$$ ($$$1 \le l_{i+1} \le r_{i+1} \le i$$$).

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
Output

For each test case, print one integer — the minimum possible number of edges in the second graph.

Example
Input
5
5
1 1
1 2
2 3
2 4
6
1 1
1 1
2 3
2 3
4 5
5
1 1
1 2
1 3
1 4
6
1 1
1 1
1 1
2 4
2 4
6
1 1
1 2
1 1
2 4
3 5
Output
4
8
4
9
6
Note

In the first test case, you can add the edges $$$1 \to 2$$$, $$$2 \to 3$$$, $$$3 \to 4$$$, and $$$4 \to 5$$$ to the second graph.

In the second test case, you can add the edges $$$1 \to 2$$$, $$$1 \to 3$$$, $$$2 \to 4$$$, $$$3 \to 4$$$, $$$2 \to 5$$$, $$$3 \to 5$$$, $$$4 \to 6$$$, and $$$5 \to 6$$$ to the second graph.