Balance

AVL Tree, a kind of binary search tree, keeps itself balanced using a property called the height balance property.

Every binary search tree that satisfies the height balance property is an AVL Tree.

For every internal vertex $v$ of a tree $T$, if the heights of the left subtree and right subtree of $v$ differ by at most 1, then $T$ is said to satisfy the height balance property.

In the figure above, the tree on the left is an AVL Tree because every internal vertex has a left subtree and right subtree of equal height.

The tree in the middle is an AVL Tree because vertices 5, 6, and 8 have left and right subtrees whose heights differ by 1, and all other vertices have a difference of 0.

The tree on the right is not an AVL Tree because vertex 8 has left and right subtrees whose heights differ by 2.

Given a positive integer $V$, write a program that prints the maximum height of an AVL Tree that can be built using at most $V$ vertices.

The first line gives the number of test cases $T$.

From the second line, $T$ lines follow, each giving the number of vertices $V$.

Print the answer over $T$ lines.

For each test case, print the maximum height of an AVL Tree that can be built with at most $V$ vertices.

• $1 \leq T \leq 1\,000$
• $1 \leq V \leq 1\,000\,000\,000$