Height and Balance of Binary Trees

You are given several binary trees in the form of their level-order traversal. Each tree is represented by a sequence of values separated by spaces, where the value null denotes an absent (empty) child. Your task is to compute two values for each tree: the height of the tree and whether the tree is balanced.

A binary tree is balanced if, for every node, the absolute difference between the heights of its left and right subtrees is at most 1. The height of an empty tree is defined as 0, and the height of a non-empty tree is the maximum height of its subtrees plus 1.

The input begins with an integer T representing the number of test cases. Each of the following T lines contains a level-order traversal of a binary tree. For each test case, output a single line with two integers: the height of the tree and a flag (1 if the tree is balanced, 0 otherwise), separated by a space.

Note: If the tree is empty (denoted by null), its height is 0 and it is considered balanced.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the following T lines contains a binary tree represented in level-order traversal. The values are separated by spaces and the string null indicates a missing node.

outputFormat

For each test case, output a single line containing two integers separated by a space. The first integer is the height of the binary tree, and the second integer is 1 if the tree is balanced or 0 otherwise.

## sample

2
3 9 20 null null 15 7
1 2 2 3 3 null null 4 4

3 1
4 0

</p>