33050번 - 19m19p19s12345675z

문제

마작패로 오늘의 운세를 점치는 방법에 대해 알고 있나요? 마작패 14ドル$장으로 이루어진 손패를 무작위로 하나 뽑아 그 손패의 마작패 문자열이 사전순으로 앞쪽일수록 운세가 좋다고 합니다. (여러분도 천봉에서 텍스트 상자 옆 신규^新規 버튼을 눌러 오늘의 운세를 점쳐볼 수 있습니다!)

마작패 문자열은 마작의 패를 쉽게 나타내기 위한 표기법입니다. 마작패는 크게 만수패, 통수패, 삭수패, 자패의 4ドル$종류로 이루어져 있으며 마작패 문자열에서 각각 m, p, s, z로 나타냅니다. 만수패, 통수패, 삭수패는 각각 9ドル$종, 자패는 7ドル$종으로 총 34ドル$종이 있고, 각 패의 마작패 문자열은 앞에 숫자를 붙여 순서대로 1m, 2m, ..., 9m, 1p, 2p, ..., 9p, 1s, 2s, ..., 9s, 1z, 2z, ..., 7z로 나타냅니다. 패 여러 장의 마작패 문자열을 나타낼 때는 이 순서에 맞추어 각 패의 마작패 문자열을 모두 이어 붙이되, 인접한 패가 같은 종류(m, p, s, z 중 하나)일 경우 종류를 나타내는 문자를 마지막에 한 번만 표기합니다.

마작패는 34ドル$종이 각각 4ドル$장씩 있어 총 136ドル$장으로 이루어져 있는데, 예외적으로 5m, 5p, 5s는 일반패 3ドル$장과 색깔이 다른 적도라패( , , ) 1ドル$장으로 이루어져 있습니다. 따라서 적도라패는 일반패와 구분하기 위해 마작패 문자열에서 0m, 0p, 0s로 나타내며, 순서상으로 해당 종류의 4와 5 사이에 위치합니다.

손패는 마작패 14ドル$장으로 이루어져 있으며, 이 중 마지막으로 손패에 추가된 패 1ドル$장을 쯔모패라 하여 나머지 패 13ドル$장과 따로 구분합니다. 손패를 마작패 문자열로 나타낼 때는 쯔모패를 순서와 상관없이 가장 마지막에 두어 표기합니다.

정수 $k$가 주어지면, 서로 다른 모든 마작패 문자열 중 사전순으로 $k$번째인 것을 찾아 주세요. 이때 ASCII 코드의 대소를 기준으로 서로 다른 문자를 비교하며, 마작패 문자열에 등장할 수 있는 모든 문자를 ASCII 코드 순서대로 나타내면 다음과 같습니다: 0123456789mpsz

입력

첫 번째 줄에 테스트 케이스의 개수를 의미하는 정수 $T$가 주어집니다. $(1 \le T \le 10,000円)$

다음 $T$개의 줄에는 문제에서 언급한 수 $k$가 주어집니다. $T$개의 줄 중 $i$번째 줄에는 $i$번째로 답을 구해야 할 $k$를 의미하는 정수 $k_i$가 주어집니다. $(1 \le k_i \le 10^{18})$

출력

$T$줄을 출력합니다. $i$번째 줄에는 모든 마작패 문자열 중 사전순으로 $k_i$번째인 것을 출력합니다. 단, $k_i$가 서로 다른 모든 마작패 문자열의 개수보다 크다면 해당 줄엔 -1을 출력합니다.

제한

노트

마작패 문자열에서 쯔모패를 제외한 패는 반드시 순서대로 나타내야 하기 때문에 01111222233334m과 같은 마작패 문자열은 존재하지 않습니다.