Problem Description

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.

2
2
1 1
1 1
2
1 1
1 3

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.