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

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

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

• Я ніколи не використовую символи *, #, 0 і 9 у своєму паролі.

• Кожна цифра в паролі використовується не більше одного разу.

• Мій пароль містить не більше 8 цифр (1 ≤ n ≤ 8, де n - кількість цифр у паролі).

• Кожна цифра i в паролі не перевищує n (пароль 132 є допустимим для n = 3, але пароль 124 недопустимий, оскільки третя цифра перевищує 3).

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Примітка

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