Trees - Height P61120

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 explained at problem "Trees — Recursive traversal", with an exception: All the values are 0, because the content of the nodes here is not important.

Output

Your program must print the height of each given tree.