Олимпиадный тренинг

Задача . B. Антифибоначчиевы перестановки


Назовем перестановку \(p\) длины \(n\) антифибоначчиевой, если для всех \(i\) (\(3 \le i \le n\)) выполняется \(p_{i-2} + p_{i-1} \ne p_i\). Напомним, что перестановкой называется массив длины \(n\), содержащий каждое целое число от \(1\) до \(n\) ровно один раз.

Ваша задача — для заданного числа \(n\) вывести \(n\) различных антифибоначчиевых перестановок длины \(n\).

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

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 48\)) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число \(n\) (\(3 \le n \le 50\)).

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

Для каждого набора входных данных выведите \(n\) строк. Каждая строка должна содержать антифибоначчиеву перестановку длины \(n\). В каждом наборе входных данных каждая перестановка должна быть выведена не более одного раза.

Если существует несколько ответов, выведите любой из них. Можно показать, что всегда существует способ найти \(n\) различных антифибоначчиевых перестановок длины \(n\), соблюдая ограничения задачи.


Примеры
№Входные данныеВыходные данные
1
2
4
3
4 1 3 2
1 2 4 3
3 4 1 2
2 4 1 3
3 2 1
1 3 2
3 1 2
Статистика успешных решений по компиляторам
 Кол-во
С++5