3071번 - The ♡ System

문제

우현이는 수학을 세상에서 제일 좋아한다. 어느 날 우현이는 서든어택을 하던 중에 Yes!!!를 외치면서 새로운 수 체계가 생각해냈다. 우현이는 자신이 사랑하는 사람의 이름을 따서 그 수 체계의 이름을 지었으나, 프라이버시 문제로 ♡진법이라고 이름 붙였다.

♡진법은 3진법과 비슷하게 나타낸다. 제일 마지막 자리부터 3⁰의 자리, 3¹의 자리, 3²의 자리… 로 나타낸다. 그리고 자리수로는 3개의 숫자 -1, 0, 1을 쓴다. 그런데 우현이는 -1이라고 쓰기가 너무 귀찮았으므로, -으로 간단하게 나타내기로 했다.

예를 들면

• 1 = 1 (1×3⁰)
• 2 = 1- (1×3¹ + (-1)×3⁰)
• 3 = 10 (1×3¹ + 0×3⁰)
• 4 = 11 (1×3¹ + 1×3⁰)
• 5 = 1-- (1×3¹ + (-1)×3¹ + (-1)×3⁰)
• 6 = 1-0 (1×3¹ + (-1)×3¹ + 0×3⁰)
• 2048 = 10-110--

이다.

10진법의 수 n이 주어지면, ♡진법으로 변환해 출력하는 프로그램을 작성하시오.

입력

입력은 총 T개의 테스트 케이스로 이루어져 있다. 첫째 줄에 테스트 케이스의 개수 T가 주어지고, 다음 T개의 줄에 10진법의 수 n (-2³⁰ ≤ n ≤ 2³⁰) 이 주어진다.

출력

각각의 테스트 케이스에 대해 한 줄에 하나씩 10진법의 수 n을 ♡진법으로 바꾼 수를 출력한다.

제한

힌트