[Solution] Permutation Chain Codeforces Solution

B. Permutation Chain

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A permutation of length n$n$ is a sequence of integers from 1$1$ to n$n$ such that each integer appears in it exactly once.

Let the fixedness of a permutation p$p$ be the number of fixed points in it — the number of positions j$j$ such that pj=j$p_j=j$, where pj$p_j$ is the j$j$-th element of the permutation p$p$.

You are asked to build a sequence of permutations a1,a2,…$a_1,a_2,\dots$, starting from the identity permutation (permutation a1=[1,2,…,n]$a_1=[1,2,\dots ,n]$). Let's call it a permutation chain. Thus, ai$a_i$ is the i$i$-th permutation of length n$n$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

For every i$i$ from 2$2$ onwards, the permutation ai$a_i$ should be obtained from the permutation ai−1$a_{i-1}$ by swapping any two elements in it (not necessarily neighboring). The fixedness of the permutation ai$a_i$ should be strictly lower than the fixedness of the permutation ai−1$a_{i-1}$.

Consider some chains for n=3$n=3$:

• a1=[1,2,3]$a_1=[1,2,3]$, a2=[1,3,2]$a_2=[1,3,2]$ — that is a valid chain of length 2$2$. From a1$a_1$ to a2$a_2$, the elements on positions 2$2$ and 3$3$ get swapped, the fixedness decrease from 3$3$ to 1$1$.
• a1=[2,1,3]$a_1=[2,1,3]$, a2=[3,1,2]$a_2=[3,1,2]$ — that is not a valid chain. The first permutation should always be [1,2,3]$[1,2,3]$ for n=3$n=3$.
• a1=[1,2,3]$a_1=[1,2,3]$, a2=[1,3,2]$a_2=[1,3,2]$, a3=[1,2,3]$a_3=[1,2,3]$ — that is not a valid chain. From a2$a_2$ to a3$a_3$, the elements on positions 2$2$ and 3$3$ get swapped but the fixedness increase from 1$1$ to 3$3$.
• a1=[1,2,3]$a_1=[1,2,3]$, a2=[3,2,1]$a_2=[3,2,1]$, a3=[3,1,2]$a_3=[3,1,2]$ — that is a valid chain of length 3$3$. From a1$a_1$ to a2$a_2$, the elements on positions 1$1$ and 3$3$ get swapped, the fixedness decrease from 3$3$ to 1$1$. From a2$a_2$ to a3$a_3$, the elements on positions 2$2$ and 3$3$ get swapped, the fixedness decrease from 1$1$ to 0$0$.

Find the longest permutation chain. If there are multiple longest answers, print any of them.

Input

The first line contains a single integer t$t$ (1≤t≤99$1\le t\le 99$) — the number of testcases.

The only line of each testcase contains a single integer n$n$ (2≤n≤100$2\le n\le 100$) — the required length of permutations in the chain.

Output

For each testcase, first, print the length of a permutation chain k$k$.

Then print k$k$ permutations a1,a2,…,ak$a_1,a_2,\dots ,a_k$. a1$a_1$ should be an identity permutation of length n$n$ ([1,2,…,n]$[1,2,\dots ,n]$). For each i$i$ from 2$2$ to k$k$, ai$a_i$ should be obtained by swapping two elements in ai−1$a_{i-1}$. It should also have a strictly lower fixedness than ai−1$a_{i-1}$.