이상한 호텔의 송이

송이가 묵고 있는 S 호텔은 60층짜리 건물이며, 구조는 완전 이진 트리로 나타낼 수 있다. 방은 트리의 노드이고, 방과 방 사이를 위아래로 잇는 계단은 간선이다. 꼭대기에 루트 노드가 있다. 두 방 사이는 계단이 있어야만 이동할 수 있고, 이동은 계단을 통해서만 가능하다.

다음 그림은 1층부터 3층까지의 방과 계단을 나타낸 것이다. 사각형은 방이고, 방과 방을 잇는 선은 계단이다. 사각형 안의 수는 방의 호수이다. 파란색 사각형 안의 수는 호텔의 모든 방을 호수 기준으로 오름차순 정렬했을 때 그 방이 몇 번째에 오는지를 나타낸다.

1층이 가장 위층이고, 아래로 내려갈수록 층 번호가 1씩 늘어나 가장 아래층은 60층이다. 1층에는 방이 1개 있고, 나머지 층에는 바로 위층 방 개수의 두 배만큼 방이 있다.

각 층의 방 번호는 1부터 시작해서 1씩 늘어난다. 그 층의 마지막 방 번호는 그 층의 방 개수와 같다. 1층을 제외한 각 층의 $i$번 방은 바로 위층의 $\lceil \frac{i}{2} \rceil$번 방과 계단으로 연결된다. 예를 들어 3층 3번 방은 2층 2번 방과 연결되어 있다.

각 방의 호수는 층 번호와 그 층에서의 방 번호를 이어 붙인 수이다. 방 번호가 18자리보다 짧으면 앞에 0을 채워 18자리로 맞춘 뒤 층 번호를 이어 붙인다. 예를 들어 3층의 마지막 방의 호수는 $3\,000\,000\,000\,000\,000\,004$이다.

길치인 송이는 호텔의 모든 방을 호수 오름차순으로 정렬했을 때 N번째 방에 있다. 송이는 전망대가 있는 1층 1번 방까지 최소한의 방만 거쳐서 이동하려 한다. 송이가 전망대까지 지나야 하는 방들의 호수를 모두 출력하여 송이를 무사히 데려다주자.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. $(1 \leq T \leq 10^4)$

각 테스트 케이스마다 송이가 있는 방의 위치를 나타내는 $N$이 한 줄에 하나씩 주어진다. $(2 \leq N \leq 10^{18})$

송이는 호텔의 모든 방을 호수 오름차순으로 정렬했을 때 N번째로 오는 방에 있다.

각 테스트 케이스마다 송이가 있는 방부터 전망대 방까지 지나야 하는 방의 호수를 한 줄에 하나씩 차례대로 출력한다.

한 테스트 케이스 안에서 이미 지나간 방은 다시 지나가면 안 된다.

그래프 이론에서 트리란 사이클이 없는 연결 그래프를 뜻한다. 트리 중에서 다음 두 조건을 만족하는 트리를 완전 이진 트리라고 한다.

• 리프 노드를 제외한 모든 노드는 정확히 두 개의 자식 노드를 갖는다.
• 리프 노드들의 깊이는 모두 같다. 노드의 깊이는 그 노드에서 루트 노드까지 도달하는 데 필요한 간선의 최소 개수이다.