*Left child, right sibling* is the name
of a known bijection between the general trees and the non empty binary trees with empty right subtree.
To convert a general tree to binary tree
the first child (starting on the left) is made its
leftmost child of each node
and the remaining nodes one after another
are made the right child of the previous sibling.

(To see an instance with a tree with the same shape than the first tree of the input-output instance, consult the pdf or ps version of this wording.)

Write a program that reads the shape of various general trees, and for each one prints the height of the corresponding binary tree.

Input

Input starts with m, the number of trees that must be treated The description of the m trees follow as is explained at the exercise , with two exceptions: The values are not given, because the content of the nodes here is not important. The number of nodes is neither given, because you do not need to store the trees in any vector to solve this exercise.

Output

Your program must print the height corresponding to the binary tree of each given tree.

Public test cases

**Input**

3 3 2 0 1 1 0 0 4 0 0 0 0 2 1 0 0 2 0 0

**Output**

8 3 3

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions