codeforces#P1644B. Anti-Fibonacci Permutation

    ID: 32739 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forceconstructive algorithmsimplementation

Anti-Fibonacci Permutation

Description

Let's call a permutation $p$ of length $n$ anti-Fibonacci if the condition $p_{i-2} + p_{i-1} \ne p_i$ holds for all $i$ ($3 \le i \le n$). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

Your task is for a given number $n$ print $n$ distinct anti-Fibonacci permutations of length $n$.

The first line contains a single integer $t$ ($1 \le t \le 48$) — the number of test cases.

The single line of each test case contains a single integer $n$ ($3 \le n \le 50$).

For each test case, print $n$ lines. Each line should contain an anti-Fibonacci permutation of length $n$. In each test case, you cannot print any permutation more than once.

If there are multiple answers, print any of them. It can be shown that it is always possible to find $n$ different anti-Fibonacci permutations of size $n$ under the constraints of the problem.

Input

The first line contains a single integer $t$ ($1 \le t \le 48$) — the number of test cases.

The single line of each test case contains a single integer $n$ ($3 \le n \le 50$).

Output

For each test case, print $n$ lines. Each line should contain an anti-Fibonacci permutation of length $n$. In each test case, you cannot print any permutation more than once.

If there are multiple answers, print any of them. It can be shown that it is always possible to find $n$ different anti-Fibonacci permutations of size $n$ under the constraints of the problem.

Samples

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