Ranking AVL trees P20941

Given a non-empty binary tree $T$, let $T_L$ and $T_R$ denote respectively the left child of $T$ and the right child of $T$. A binary tree $T$ is an AVL tree if and only if $T$ is empty, or $T_L$ and $T_R$ are AVL trees such that $\vert \mbox{height}(T_L) - \mbox{height}(T_R) \vert \le 1$. These are some examples of AVL trees with respective heights 0, 1, 2, 2, 2, 3 and 3 (a box denotes an empty tree):

We can inductively define a total order over AVL trees as follows: The empty tree is the smallest AVL tree. For every two non-empty AVL trees $A$ and $B$, $A < B$ if and only if

• $\mbox{height}(A) < \mbox{height}(B)$, or

• $\mbox{height}(A) = \mbox{height}(B)$ and $A_L < B_L$, or

• $\mbox{height}(A) = \mbox{height}(B)$ and $A_L = B_L$ and $A_R < B_R$.

The trees in the picture above are the first, second, ... , seventh AVL trees using this order.

Write a program such that, for every given AVL tree, computes and prints its rank (that is, its position in the infinite sorted list of AVL trees, starting at 1).

Input

Input begins with the number of cases $n$, followed by $n$ strings, each one with the preorder of an AVL tree, with ‘1’ denoting a node and ‘0’ denoting a leaf. No given tree has height larger than 6.

Output

For every given AVL tree, print its rank.