AVL Tree Height Tracker

This problem requires you to implement an AVL Tree insertion algorithm. An AVL Tree is a self-balancing binary search tree where the balance factor of every node is maintained by ensuring that the difference between the heights of its left and right subtrees is at most 1. The balance factor is computed using the formula: $$Balance = Height(left) - Height(right)$$.

For each test case, you are given a sequence of integers. Starting with an empty tree, insert the integers one by one into the AVL tree. After each insertion, record the height of the resulting AVL tree using the formula: \(\text{recorded height} = \text{(node height)} - 1\). Note that a single-node tree has a height of 1, and therefore its recorded height is 0.

Your task is to simulate the insertion process and output the recorded height after each insertion for every test case.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case is described on a single line containing an integer \(N\) (the number of elements), followed by \(N\) space-separated integers. These integers are to be inserted into the AVL tree in the given order.

outputFormat

For each test case, output a single line of space-separated integers. Each integer is the recorded height of the AVL tree (i.e. node height minus 1) after each insertion.

## sample

3
3 10 20 30
4 20 4 26 3
5 3 2 1 4 5

0 1 1
0 1 1 2
0 1 1 2 2

</p>