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 | height(T_{L}) − height(T_{R}) | ≤ 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 A
_{L}< B_{L}, or - height(A) = 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.

Public test cases

**Input**

3 100 110010100 11111100010011000111000100111100010011000

**Output**

2 6 6736354888

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++