如果条件 $$$p_{i-2} + p_{i-1} \ne p_i$$$ 对所有 $$$i$$$ ($$$3 \le i \le n$$$) 成立,我们将长度 $$$n$$$ 的排列 $$$p$$$ 称为反斐波那契排列。回想一下,排列是长度为 $$$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
输出 #1
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