Binary Tree Height Calculation

Problem Description

You are given a level-order traversal of a binary tree where -1 represents a null node. Your task is to calculate the height of the binary tree.

The height of a binary tree is defined as the length (number of nodes) of the longest path from the root to a leaf. Note that if the tree is empty (i.e., the first element is -1), its height is 0.

The level-order traversal is provided in such a way that for each test case, the first number indicates the number of nodes in the traversal list, followed by that many integers.

For example, consider the level order: [3, 9, 20, -1, -1, 15, 7]. The height of the corresponding binary tree is 3.

---

Note: All formulas in explanations should be interpreted as follows: the height of a non-empty tree can be computed as

$$H = \max(H_{left}, H_{right}) + 1,$$

where Hleft and Hright are the heights of the left and right subtrees respectively.

inputFormat

Input Format

The first line contains an integer T, the number of test cases.

For each test case, the first integer is N which indicates the number of elements in the level-order traversal of the tree. The next N integers represent the nodes of the tree in level-order, where -1 denotes a null node.

Example

5
7 3 9 20 -1 -1 15 7
5 1 -1 2 -1 -1
1 1
1 -1
11 1 2 3 4 5 6 7 8 9 10 11

outputFormat

Output Format

For each test case, output a single line containing the height of the corresponding binary tree.

Example

3
2
1
0
4

## sample

5
7 3 9 20 -1 -1 15 7
5 1 -1 2 -1 -1
1 1
1 -1
11 1 2 3 4 5 6 7 8 9 10 11

3
2
1
0
4

</p>