21968번 - 선린의 터를

문제

드높은 남산 위에 우뚝 선

(중략)

세워라 반석 위에

선린의 터를

1899년, 여러분들은 대한제국 고종 황제의 칙령을 받아 한국 최초의 실업교육기관인 관립상공학교를 세울 터를 선택해야 한다.

대한제국에서 학교를 지을만한 터는 여러 개 있는데, 각 터는 서로 다른 자연수를 번호로 갖고 있다. 특히, 선린의 터의 번호는 3ドル^k$꼴의 자연수가 최대 한 번씩 더해진 자연수이다(단, $k \ge 0$). 즉, 선린의 터의 번호는 1ドル(=3^0), 3(=3^1), 9(=3^2), 27(=3^3), 81(=3^4), 90(=3^2+3^4), 91(=3^0+3^2+3^4)$ 등이 있다.

여러분은 $N$번째로 작은 선린의 터를 탐색하라는 명령을 받았다. $N$번째 선린의 터를 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 여러분들이 찾아야 하는 선린의 터의 개수 $T$가 주어진다.

두 번째 줄부터 $T$개의 줄에 여러분들이 찾아야 하는 선린의 터에 대한 정보 $N$이 주어진다.

출력

여러분들이 찾아야 하는 선린의 터의 번호를 한 줄에 하나씩 차례대로 출력한다.

제한

1ドル \leq T \leq 1,000円$

1ドル \leq N \leq 123,456円,789円,123円$

힌트

입력으로 주어지는 수와 출력해야 하는 정답이 매우 크기 때문에 64비트 자료형(C/C++은 long long, Java는 long, %lld로 출력)을 사용해야 한다.