29702번 - 이상한 호텔의 송이

문제

송이가 묵고 있는 S 호텔은 60ドル$층짜리 건물인데, 이 호텔의 구조는 완전 이진 트리의 형태로 나타낼 수 있다. 호텔에 있는 방들을 트리의 노드로, 방과 방 사이를 위아래로 잇는 계단을 간선으로 생각한다면, 이 호텔의 구조는 가장 꼭대기에 루트 노드가 있는 완전 이진 트리의 형태이다. 이때, 방과 방 사이를 이동하기 위해서는 두 방 사이를 잇는 계단이 존재해야 하며 계단을 통해서만 이동이 가능하다.

다음 그림은 이 호텔의 1ドル$층부터 3ドル$층 사이에 존재하는 방과 계단을 나타낸 것이다. 그림에서 직사각형으로 표현된 노드는 방이고 방과 방을 잇는 선은 계단을 의미한다. 직사각형 안에 쓰여있는 수는 그 방의 호수이다. 또, 파란색 사각형 안의 수는 호텔에 있는 모든 방을 호수를 기준으로 오름차순 정렬했을 때 몇 번째로 오는지를 나타내는 수이다.

이 호텔은 특이하게도 가장 꼭대기 층이 1ドル$층이고, 아래로 내려올수록 층의 번호가 1ドル$씩 증가하여 가장 아래쪽 층은 60ドル$층이다. 완전 이진 트리 구조를 갖는 이 호텔에는, 1ドル$층에 1ドル$개의 방이, 1ドル$층을 제외한 나머지 층에는 층마다 바로 위층에 존재하는 방 개수의 두 배만큼의 방이 존재한다.

이 호텔의 각 층에는 방마다 번호가 붙어 있다. 각 층의 방 번호는 1ドル$부터 시작해서 1ドル$씩 증가하여, 그 층의 가장 마지막 방의 방 번호는 해당 층에 존재하는 방의 개수와 같다. 또, 1ドル$층을 제외한 각 층의 $i$번 방은 바로 위층의 $\lceil \frac{i}{2} \rceil$번 방과 계단으로 연결되어 있다. 예시로 3ドル$층 3ドル$번 방은 2ドル$층 2ドル$번 방과 계단으로 연결되어 있다는 사실을 위의 그림에서 확인할 수 있다.

이 호텔의 각 방의 호수는, 그 방이 위치하는 층의 번호와 해당 층에서 그 방의 번호를 이어 붙인 수이다. 이때, 방 번호가 18ドル$자리보다 더 작은 자리의 수라면, 18ドル$자리가 되도록 앞에 0ドル$을 붙인 뒤 층수와 이어 붙인다. 예를 들면 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$번째로 오는 방에 있다.

출력

각 테스트 케이스마다 현재 송이가 있는 방과 전망대 방을 포함하여 송이가 지나야 하는 방의 호수를 한 줄에 하나씩 차례대로 출력한다.

단, 한 테스트 케이스 내에서 송이가 한 번 지나갔던 방을 다시 지나가서는 안된다.

제한

힌트

그래프 이론에서 트리란, 사이클이 없는 연결 그래프를 의미한다. 트리 중에서도 특별히 다음 두 조건을 만족하는 트리를 완전 이진 트리라고 말한다.

• 리프 노드(잎 노드)를 제외한 모든 노드들은 정확히 두 개의 자식 노드를 갖는다.
• 리프 노드들의 깊이는 모두 동일하다. (단, 트리에서 어떤 노드의 깊이란, 그 노드로부터 루트 노드까지 도달하는 데에 필요한 간선의 최소 개수로 정의된다.)