Открыть мой сейф
Я забыл пароль своего сейфа. А в нем столько много денег! Помогите мне открыть сейф. Клавиатура выглядит следующим образом.
Я не помню длину своего пароля. Поэтому Вам придется подбирать пароли различной длины. Однако есть некоторые подсказки, которые я смог вспомнить.
Я никогда не использую символы *, #, 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.