큐브비트

새 컴퓨터가 도착했다. 그런데 주문할 때 실수가 있었다. 큐비트로 동작하는 기계를 주문한 줄 알았는데, 실제로 도착한 것은 큐브비트로 동작하는 컴퓨터 수백 대였다.

준비해 둔 프로그램과 데이터는 모두 10진법으로 작성되어 있다. 새 컴퓨터는 3진법으로 수를 세므로, 데이터를 입력하려면 먼저 3진법으로 바꿔야 한다.

10진수의 흐름을 읽어 새 컴퓨터의 입력 버스에 맞는 3진수로 바꾸는 프로그램을 작성하라.

입력은 다음과 같이 주어진다.

• 첫째 줄에 데이터 흐름의 크기인 정수 $n$ ($1 \le n \le 10^6$)이 주어진다.
• 다음 $n$개의 줄에 10진 정수 $v_i$ ($0 \le v_i < 3^{20}$)가 한 줄에 하나씩 주어진다. $v_i$는 데이터 흐름의 $i$번째 정수를 10진법으로 나타낸 것이다.

$n$개의 줄에 걸쳐 각 수를 3진법으로 바꾼 결과를 입력과 같은 순서로 출력한다. 디스크 공간을 아끼기 위해 앞에 오는 0은 출력하지 않는다. 값이 0이면 0 하나만 출력한다.