Who’s 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 a single ordered pair (t1, t2) of two binary trees, left subtree t1 and right subtree t2 respectively, called an internal node ‘◦’. Given an integer n, B(n) is the set of trees with n leaves. For instance, the picture below shows the two trees of B(3) = {(•, (•, •)), ((•; , •), •)}.
Observe that those trees both have two internal nodes and a total of five nodes. Given a tree t we define its unique integer identifier N(t):
- N(•)=0
- N(t1, t2) = 2n1+n2 + 2n2 N(t1) + N(t2), where n1 and n2 are the number of nodes in t1 and t2
respectively.
For instance, we have N(•,•) = 22 +21 ×0+0 = 4, N(•,(•,•)) = 24 +23 ×0+4 = 20 and N((•,•),•)=24 +21 ×4+0=24.
The ordering ⪰ is defined on binary trees as follows: •⪰t
(t1,t2) ⪰ (u1,u2), whent1 ⪰u1 andt1 ̸=u1, ort1 =u1 andt2 ⪰u2 Hence for instance, (•, (•, •)) ⪰ ((•, •), •) holds, since we have • ⪰ (•, •).
Using the ordering ⪰, B(n) can be sorted. Then, given a tree t in B(n), we define S(t) as the tree that immediately follows t in the sorted presentation of B(n), or as the smallest tree in B(n), if t is maximal in B(n). For instance, we have S(•, •) = (•, •) and S(•, (•, •)) = ((•, •), •). By composing the inverse of N,S and N we finally define a partial map on integers.
s(k) = N(S(N−1(k))) Write a program that computes s(k).
Input
The first input line contains an integer K, with K > 0. It is followed by K lines, each specifying an integer ki with 1 ≤ i ≤ K and 0 ≤ ki < 231.
2/2 Output
The output should consist of K lines, the i-th output line being s(ki), or ‘NO’ if s(ki) does not exist. Sample Input
5
4
0 20 5 432
Sample Output
4
0 24 NO 452