[Solution] Anti-Fibonacci Permutation solution codeforces

Anti-Fibonacci Permutation solution codeforces – Let’s call a permutation 𝑝p of length 𝑛n anti-Fibonacci if the condition 𝑝𝑖2+𝑝𝑖1𝑝𝑖pi−2+pi−1≠pi holds for all 𝑖i (3𝑖𝑛3≤i≤n). Recall that the permutation is the array of length 𝑛n which contains each integer from 11 to 𝑛n exactly once.

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

Anti-Fibonacci Permutation solution codeforces

The first line contains a single integer 𝑡t (1𝑡481≤t≤48) — the number of test cases.

The single line of each test case contains a single integer 𝑛n (3𝑛503≤n≤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.

Anti-Fibonacci Permutation solution codeforces

output

Copy
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

Leave a Comment