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