eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Открыть мой сейф

Открыть мой сейф

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb6953

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

  • Я никогда не использую символы \*, \#, 0 и 9 в моем пароле.

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

  • Мой пароль содержит не более 8 цифр (1n8, где n - количество цифр в пароле).

  • Каждая цифра i в пароле имеет значение, не большее n (пароль 132 является допустимым для n = 3, однако пароль 124 уже недопустим, так как третья цифра превышает 3).

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

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

Входные данные

Первая строка содержит количество тестов t (1t6). Далее следуют t тестов. Каждый тест содержит количество цифр n (1n8) в пароле.

Выходные данные

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

Объяснение

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

Пример

Входные данные #1
3
2
3
1
Выходные данные #1
12
213
1
Автор Dr. Apichat Heednakram
Источник 2013 ACM-ICPC Thailand Southern Programming Contest, Август 10, Задача A