시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 34 19 12 48.000%

문제

The new computers are here! However, we made a mistake during the order: we thought we were ordering machines with qubits; in fact, we ordered several hundred computers powered by cube-bits.

The programs and data we had ready were prepared in base 10. To feed the data into the new computer, which uses a cubic system of counting, we will need to convert it to base 3 first.

Write a program to convert a stream of decimal numbers into ternary format, so they fit the new system’s input bus.

입력

The input consists of:

  • One line with an integer n (1 ≤ n ≤ 106), the size of the data stream.
  • n lines with one decimal integer vi (0 ≤ v < 320), the decimal representation of the i-th integer in the data stream.

출력

Output n lines, giving the numbers converted to base-3, in the same order as given. In the interest of conserving disk space, do not print leading zeroes.

예제 입력 1

4
12
14
13
15

예제 출력 1

110
112
111
120

예제 입력 2

2
2147483648
3486784400

예제 출력 2

12112122212110202102
22222222222222222222