[Solution] Permutation Codeforces Solution | Codeforces 2022

B. Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recall that a permutation of length n$n$ is an array where each element from 1$1$ to n$n$ occurs exactly once.

For a fixed positive integer d$d$, let's define the cost of the permutation p$p$ of length n$n$ as the number of indices i$i$ (1≤i<n)$(1\le i<n)$ such that pi⋅d=pi+1$p_i\cdot d=p_{i+1}$.

For example, if d=3$d=3$ and p=[5,2,6,7,1,3,4]$p=[5,2,6,7,1,3,4]$, then the cost of such a permutation is 2$2$, because p2⋅3=p3$p_2\cdot 3=p_3$ and p5⋅3=p6$p_5\cdot 3=p_6$.

Your task is the following one: for a given value n$n$, find the permutation of length n$n$ and the value d$d$ with maximum possible cost (over all ways to choose the permutation and d$d$). If there are multiple answers,

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 then print any of them.

Input

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

Grass Field Codeforces Solution

Permutation Codeforces Solution

Schedule Management Codeforces Solution

Permutation Restoration Codeforces Solution

Text Editor Codeforces Solution

Points Codeforces Solution 

The single line of each test case contains a single integer n$n$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$).

The sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print the value d$d$ in the first line, and n$n$ integers in the second line — the permutation itself. If there are multiple answers, then print any of them.