B. Антифибоначчиевы перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем перестановку $$$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$$$, соблюдая ограничения задачи.

Пример
Входные данные
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