Extend-Tree

There are many questions about the tree, most of them are Binary tree. But now, I’m tired of it. In this problem, we will not talk about the binary tree again, we discuss the tree which has three sub-trees, we called it extend tree;

The extend tree is orderly, it means that every integer n(n>=0) correspond to one unique extend tree and each extend tree correspond to one unique number. The tree is numbered using the following scheme:

1. The empty tree is numbered 0;
2. The single-node tree is numbered 1;
3. All extend trees that has m nodes correspond to a smaller integer than the tree which has more than m nodes.
4. Any extend tree having m nodes with left, mid and right sub-trees L ,M and R is numbered n; such that all trees having m nodes numbered > n have either Left sub-trees numbered higher than L, or A left sub-tree = L and a mid sub-tree numbered higher than M, or a left sub-tree = L a mid sub-tree = M and a right sub-tree numbered higher than R.

The first 18 extend trees are show below:



Your job for this problem is to output a extend tree when its order number is given.

The first line contains a single positive integer T( T <= 3000 ), indicating the number of datasets.
Each instance consist of a single integer n, where 1<= n <=10^14.

For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:
A tree with no children should be output as X. A tree with left, mid and right sub-trees L M, and R should be output as (L)(M)(R)X, where L M, and R are the representations of L M, and R.
If L is empty, just output (M)(R)X.
If M is empty, just output (L)(R)X.
If R is empty, just output (L)(M)X.
If L and M is empty, just output (R)X.
...
The answer of other conditions has the same format.

10
1
2
3
4
5
6
7
8
9
10

Case #1: X
Case #2: (X)X
Case #3: (X)X
Case #4: (X)X
Case #5: ((X)X)X
Case #6: ((X)X)X
Case #7: ((X)X)X
Case #8: (X)(X)X
Case #9: ((X)X)X
Case #10: ((X)X)X

2011 Multi-University Training Contest 9 - Host by BJTU