I2R03. AVL trees P13827

Your task is to write a program that reads the shape of many general trees and, for each one, computes its height and decides if it is an AVL tree or not. We say that a tree is AVL if and only if

• it has only one node;

• or it has more than one node, all its children are AVL, and the difference between the heights of these children is at most one;

Input

The input starts with $m$, the number of trees that must be treated. The description of the $m$ trees follows as it is explained at the exercise REREG of the collection, with two exceptions: the values are not given, because the contents of the nodes are not important here. The number of nodes is not given either, because it is not necessary to store the trees in any vector to solve this exercise.

Output

Your program must print one line for each tree of the input, with its height, and the indication of it is an AVL tree or not. Follow the format of the instance.