내 금고 열기

금고 비밀번호를 잊어버렸다. 안에 돈이 잔뜩 들어 있으니 금고 여는 것을 도와 달라. 키패드는 이렇게 생겼다.

비밀번호가 몇 자리인지도 기억나지 않아서 자릿수를 바꿔 가며 시도해 봐야 한다. 그래도 떠오르는 힌트가 몇 가지 있다.

• 비밀번호에 *, #, 0, 9는 한 번도 쓴 적이 없다.
• 비밀번호의 각 자리 숫자는 모두 다르다. 같은 숫자가 두 번 이상 나오지 않는다.
• 비밀번호는 최대 8자리다. 자릿수를 $N$이라 하면 $1 \le N \le 8$이다.
• 비밀번호의 각 자리 숫자는 항상 $N$ 이하다. 예를 들어 $N = 3$이면 132는 올바르지만 124는 셋째 자리가 3을 넘으므로 올바르지 않다.

이 조건을 만족하는 순열을 모두 만들면 순열 하나가 금고를 열어 볼 비밀번호 후보 하나가 된다. 진짜 비밀번호는 정렬한 순열 배열에서 인덱스 $\lfloor L / 3 \rfloor$ 자리에 놓여 있다. 여기서 $L$은 후보 전체의 개수이고 나눗셈은 정수 나눗셈이다. 배열은 오름차순으로 정렬하고, 인덱스는 1이 아니라 0부터 센다.

자릿수가 주어지면 진짜 비밀번호를 찾는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 6$). 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 비밀번호의 자릿수 $N$ 하나로 이루어진다 ($1 \le N \le 8$).

각 테스트 케이스마다 $N$자리 비밀번호를 한 줄에 하나씩 출력한다.

$N = 3$인 경우를 보자. 정렬한 순열은 123, 132, 213, 231, 312, 321이고 개수는 $L = 6$이다. 비밀번호의 위치는 정수 나눗셈으로 $6 / 3 = 2$이고, 인덱스를 0부터 세므로 답은 213이다.