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) $ \bullet$; 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) = {($ \bullet$,($ \bullet$,$ \bullet$)),(($ \bullet$;,$ \bullet$),$ \bullet$)}.

\epsfbox{p2943.eps}

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($ \bullet$) = 0
  2. N(t1, t2) = 2n1 + n2 + 2n2N(t1) + N(t2), where n1 and n2 are the number of nodes in t1 and t2 respectively.

For instance, we have N($ \bullet$,$ \bullet$) = 22 + 21×0 + 0 = 4, N($ \bullet$,($ \bullet$,$ \bullet$)) = 24 + 23×0 + 4 = 20 and N(($ \bullet$,$ \bullet$),$ \bullet$) = 24 + 21×4 + 0 = 24.

The ordering $ \succeq$ is defined on binary trees as follows:

$\displaystyle \bullet$ $\displaystyle \succeq$ t  
(t1, t2) $\displaystyle \succeq$ (u1, u2), when t1 $\displaystyle \succeq$ u1, or t1 = u1 and t2 $\displaystyle \succeq$ u2  

Hence for instance, ($ \bullet$,($ \bullet$,$ \bullet$)) $ \succeq$ (($ \bullet$,$ \bullet$),$ \bullet$) holds, since we have $ \bullet$ $ \succeq$ ($ \bullet$,$ \bullet$).


Using the ordering $ \succeq$, 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($ \bullet$,$ \bullet$) = ($ \bullet$,$ \bullet$) and S($ \bullet$,($ \bullet$,$ \bullet$)) = (($ \bullet$,$ \bullet$),$ \bullet$). By composing the inverse of N,S and N we finally define a partial map on integers.

s(n) = N(S(N-1(n)))

Write a program that computes s(n).

Input 

Input consists of several test cases, each of them following the description below. A blank line separates two consecutive cases.

The first input line contains an integer K, with K > 0. It is followed by K lines, each specifying an integer ni with 1$ \le$i$ \le$K and 0$ \le$ni < 231.

Output 

For each test case, the output should consist of K lines, the i-th output line being s(ni), or `NO' if s(ni) does not exist.

The outputs of two consecutive cases will be separated by a blank line.

Sample Input  

5
4
0
20
5
432

Sample Output  

4
0
24
NO
452