Я забыл пароль своего сейфа. А в нем столько много денег! Помогите мне открыть сейф. Клавиатура выглядит следующим образом.

Я не помню длину своего пароля. Поэтому Вам придется подбирать пароли различной длины. Однако есть некоторые подсказки, которые я смог вспомнить.

• Я никогда не использую символы *, #, 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.