Height of trees P83588

Write a program that reads the shape of various binary trees, and prints the height of each one. We define the height of a tree as the maximal number of nodes of the paths that go from the root to each leaf (or zero, if the tree is empty).

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: all the values are 0, 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 of each given tree.