# Ranking AVL trees P20941

Statement html

Given a non-empty binary tree T, let TL and TR 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 TL and TR are AVL trees such that | height(TL) − height(TR) | ≤ 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

• height(A) < height(B), or
• height(A) = height(B) and AL < BL, or
• height(A) = height(B) and AL = BL and AR < BR.

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.

Public test cases
• Input

```3
100
110010100
11111100010011000111000100111100010011000
```

Output

```2
6
6736354888
```
• Information
Author