선린의 터

드높은 남산 위에 우뚝 선

(중략)

세워라 반석 위에

선린의 터를

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로 출력)을 써야 한다.