Calcuate the longest simple path of a cactus which supports adding nodes and circles.
Input
First line contains a single integer $Cases \leq 5$ which denotes the number of test cases.
For each case , first line contains a single integer $T$ which denotes the number of operations.
Note nodes number with 1.Firstly,we only have one node numbered 1.
For each operation, there are two positive integer $x$ and $g$,which denote the linked node and the number of adding nodes.
We let p donates the number of nodes before adding.
If g=1 , we add a node which links p+1 .
If g>1 , we add a circle p+1,p+2,...,p+g ,p+1 and p+g link with x ,p+i links with p+i+1 $(1 \leq i < g)$.
The number of added nodes for each case not exceeding $10^{5}$.
Output
For each case, output the answer after operating in a single line.
Sample Input
2
2
1 1
1 1
2
1 1
1 3
Sample Output
1
2
1
4
Hint
A simple path is a path in a graph which does not have repeating vertices.
The cactus is a graph which each edge belong to at most one simple circle.
