SP88 TREE2 - Which is Next

Every computer science student knows binary trees. Here is one of many possible definitions of binary trees. Binary trees are defined inductively. A binary tree t is either an external node (leaf)  or an ordered pair t = (t $ _{1} $ , t $ _{2} $ ) representing an internal node  with two subtrees attached, left subtree t $ _{1} $ and right subtree t $ _{2} $ . Under this definition the number of nodes in any binary tree is odd. Given an odd integer n let B(n) denote the set of all binary trees with n nodes, both internal and external. For instance B(1) consists of only one tree , B(3) = {(, )} and B(5) = {(, (, )), ((, ), )}. The trees of B(5) are depicted in the figure below.  Denote by |t| the number of nodes in a tree t. Given a tree t we define its unique integer identifier N (t) as follows: - N () = 0 - N (t $ _{1} $ , t $ _{2} $ ) = 2 $ ^{|t1|+|t2|} $ + 2 $ ^{|t2|} $ \* N(t $ _{1} $ ) +N (t $ _{2} $ )

The input begins with the integer t, the number of test cases. Then t test cases follow. For each test case the first and only line of the input contains one integer n (0

For each test case the first and only line of the output should contain one integer s - the identifier of the successor of t in B(|t|).