Відкрити мій сейф#6953

Відкрити мій сейф

1 секунда

128 мегабайтів

Дуже легка

Я забув пароль від свого сейфа, а там стільки грошей! Допоможіть мені відкрити його. Клавіатура виглядає ось так.

Я не пам'ятаю, якої довжини мій пароль. Тому вам доведеться перевіряти паролі різної довжини. Проте, я згадав кілька підказок:

Я ніколи не використовую символи *, #, $0$ і $9$ у своєму паролі.
Кожна цифра в паролі використовується не більше одного разу.
Мій пароль містить не більше $8$ цифр ( $1 \leq n \leq 8$ 1 \leq n \leq 8, де $n$ - кількість цифр у паролі).
Кожна цифра $i$ в паролі не перевищує $n$ (пароль $132$ є допустимим для $n = 3$ n = 3, але пароль $124$ недопустимий, оскільки третя цифра перевищує $3$ ).

Використовуючи цю інформацію, згенеруйте всі можливі перестановки. Кожна перестановка відповідає одній спробі вгадати пароль і відкрити сейф. Важливо, що правильний пароль знаходиться в позиції $L \3$ у відсортованому наборі перестановок, де $L$ - загальна кількість можливих перестановок, $\$ - операція цілочисельного ділення. Набір перестановок відсортований у зростаючому порядку, перша перестановка має номер $0$ (а не $1$ ).

Напишіть програму, яка знайде правильний пароль заданої довжини (довжина - це кількість цифр у паролі).

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $1 \leq t \leq 6$ 1 \leq t \leq 6). Далі йдуть $t$ тестів. Кожен тест містить кількість цифр $n$ ( $1 \leq n \leq 8$ 1 \leq n \leq 8) у паролі.

Вихідні дані

Для кожного тесту виведіть в окремому рядку $n$ -цифровий пароль.

Приклади

Приклад 1

Примітка

У задачі наведено $3$ тести. У другому тесті відсортовані перестановки виглядають так: { $123$ , $132$ , $213$ , $231$ , $312$ , $321$ }. Пароль знаходиться в позиції $6\3 = 2$ 6 \backslash 3 = 2 (цілочисельне ділення). Оскільки індекси перестановок починаються з $0$ , то паролем є $213$ .