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):

1. N(•)=0
2. 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