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 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.

Public test cases

**Input**

9 1 0 2 0 0 1 1 0 2 0 1 1 0 2 1 1 1 0 2 1 1 0 0 1 1 1 1 0 3 0 0 0 0 3 1 1 0 0 1 0

**Output**

height 2, is avl height 2, is avl height 3, is avl height 4, is not avl height 5, is not avl height 5, is avl height 2, is avl height 1, is avl height 4, is not avl

Information

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