Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Попав на аудиенцию к императору Эмгыру в захваченном нильфгаардцами королевском дворце в Вызиме, Геральт обратил внимание на убранство тронного зала. Главное украшение зала — висящие в линию флаги различных имперских провинций.
Император дал камергеру Мерериду следующие распоряжения: во-первых, каждый день флаги должны висеть в каком-нибудь новом порядке; во-вторых, никакой флаг не должен занимать одно и то же место два дня подряд. Чтобы не придумывать подходящий порядок флагов каждый день, Мерерид решил придумать единственную перестановку, согласно которой слуги будут каждый день перевешивать флаги. Перестановкой `N` флагов назовем упорядоченный набор `p_i`, содержащий каждое число от `1` до `N` ровно один раз. Если в некоторый день флаг находится на позиции `i`, то на следующий день он перемещается на позицию `p_i`.
Чтобы император был доволен, в первые `T` дней все порядки флагов должны быть попарно различны. В этом случае к моменту первого повторения император успеет забыть, что такой порядок уже был раньше. Помогите Мерериду определить минимально необходимое для этого число флагов и постройте соответствующую перестановку.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число `Q` (`1 <= Q <= 10^5`) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных содержит единственное целое число `T` (`2 <= T <= 10^{18}`) — минимальное количество дней, в течение которого порядок флагов не должен повторяться.
Для каждого набора входных данных выведите две строки.
В первой строке выведите целое число `N` — минимальное требуемое количество флагов.
Во второй строке выведите подходящую перестановку, состоящую из чисел от `1` до `N` включительно. Если подходящих перестановок несколько, выведите любую из них. Гарантируется, что сумма минимальных возможных значений `N` по всем наборам входных данных в одном тесте не превосходит `10^6`.
```sample Пример ввода
3
2
5
8
```
```sample Пример вывода
2
2 1
5
2 3 1 5 4
7
2 3 1 5 6 7 4
```
Пояснение к первому набору. Если в первый день флаги имеют порядок `1 2`, то во второй – `2 1`. Таким образом, в первые `2` дня порядки различны, как это и требовалось.
Пояснение ко второму набору. Линии флагов в первые `5` дней будут выглядеть так: `1 2 3 4 5`, `3 1 2 5 4`, `2 3 1 4 5`, `1 2 3 5 4`, `3 1 2 4 5` (порядки не повторяются, никакой флаг не остаётся на месте). Можно показать, что никакой набор из `4` и меньше флагов не обеспечит выполнения требуемых условий.
Начало
Рабочее место участника
Простые числа, разложение на множители