다음과 과정을 거쳐서 바이너리 트리에 번호를 붙일 수 있다.

• 비어있는 트리의 번호는 0이다.
• 노드가 1개인 트리는 1번이다.
• 노드가 m개인 바이너리 트리의 번호는 m+1개인 트리의 번호보다 작다.
• 노드가 m개이고, 왼쪽과 오른쪽 서브트리가 각각 L과 R인 바이너리 트리의 번호 n은 아래와 같은 두 조건 중 하나라도 만족하는 트리보다 번호가 작다. 
  • 왼쪽 서브 트리가 L보다 번호가 크다. 또는
  • 왼쪽 서브 트리가 L과 같고, 오른쪽 서브트리가 R보다 번호가 크다.
  </ul> </li>

  처음 10개 바이너리 트리와 20번째 바이너리 트리를 그림으로 그려보면 아래와 같다.

          0  1  2      3  4      5      6      7      8  9        ...     20
  
             X  X      X  X      X      X      X      X  X                 X
                 \    /    \      \    / \    /      /    \               /
                  X  X      X      X  X   X  X      X      X             X
                             \    /           \    /        \           / \
                              X  X             X  X          X         X   X
                                                              \
                                                               X
  

  n이 주어졌을 때, n번째 바이너리 트리를 구하는 프로그램을 작성하시오.

  입력 형식

  입력은 여러 개의 테스트 케이스로 이루어져 있으며, n이 하나 주어진다. (1 ≤ n ≤ 500,000,000) n=0인 경우에 프로그램을 종료하면 된다.

  출력 형식

  각각의 n에 대해서, 트리를 아래와 같이 출력한다.

  • 자식이 없는 트리는 x로 출력한다.
  • 왼쪽, 오른쪽 서브트리가 L과 R이고, 각각을 출력한 결과가 L', R'일 때, (L')x(R')을 출력한다.
    • L이 비어잇으면 X(R')을 출력한다.
    • R이 비어있으면 (L')x를 출력한다.
    </ul> </li>

    예제 입력

    1
    20
    31117532
    0

    예제 출력

    X
    ((X)X(X))X
    (X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)