## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ is a sequence of integers from $1$ to $n$ such that each integer appears in it exactly once.

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

You are asked to build a sequence of permutations ${a}_{1},{a}_{2},\dots$, starting from the identity permutation (permutation ${a}_{1}=\left[1,2,\dots ,n\right]$). Let's call it a permutation chain. Thus, ${a}_{i}$ is the $i$-th permutation of length $n$.

Solution Click Below:-  👉

👇👇👇👇👇

occupied

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

Consider some chains for $n=3$:

• ${a}_{1}=\left[1,2,3\right]$${a}_{2}=\left[1,3,2\right]$ — that is a valid chain of length $2$. From ${a}_{1}$ to ${a}_{2}$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $3$ to $1$.
• ${a}_{1}=\left[2,1,3\right]$${a}_{2}=\left[3,1,2\right]$ — that is not a valid chain. The first permutation should always be $\left[1,2,3\right]$ for $n=3$.
• ${a}_{1}=\left[1,2,3\right]$${a}_{2}=\left[1,3,2\right]$${a}_{3}=\left[1,2,3\right]$ — that is not a valid chain. From ${a}_{2}$ to ${a}_{3}$, the elements on positions $2$ and $3$ get swapped but the fixedness increase from $1$ to $3$.
• ${a}_{1}=\left[1,2,3\right]$${a}_{2}=\left[3,2,1\right]$${a}_{3}=\left[3,1,2\right]$ — that is a valid chain of length $3$. From ${a}_{1}$ to ${a}_{2}$, the elements on positions $1$ and $3$ get swapped, the fixedness decrease from $3$ to $1$. From ${a}_{2}$ to ${a}_{3}$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $1$ to $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$ ($1\le t\le 99$) — the number of testcases.

The only line of each testcase contains a single integer $n$ ($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$.

Then print $k$ permutations ${a}_{1},{a}_{2},\dots ,{a}_{k}$${a}_{1}$ should be an identity permutation of length $n$ ($\left[1,2,\dots ,n\right]$). For each $i$ from $2$ to $k$${a}_{i}$ should be obtained by swapping two elements in ${a}_{i-1}$. It should also have a strictly lower fixedness than ${a}_{i-1}$.