[Solution] Woeful Permutation Codeforces Solution

B. Woeful Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a positive integer 𝑛

Find any permutation 𝑝$p$ of length 𝑛$n$ such that the sum lcm(1,𝑝1)+lcm(2,𝑝2)+…+lcm(𝑛,𝑝𝑛)$\mathrm{lcm}(1,p_1)+\mathrm{lcm}(2,p_2)+\dots +\mathrm{lcm}(n,p_n)$ is as large as possible.

Here lcm(𝑥,𝑦)$\mathrm{lcm}(x,y)$ denotes the least common multiple (LCM) of integers 𝑥$x$ and 𝑦$y$.

A permutation is an array consisting of 𝑛$n$ distinct integers from 1$1$ to 𝑛$n$ in arbitrary order. For example, [2,3,1,5,4]$[2,3,1,5,4]$ is a permutation, but [1,2,2]$[1,2,2]$ is not a permutation (2$2$ appears twice in the array) and [1,3,4]$[1,3,4]$ is also not a permutation (𝑛=3$n=3$ but there is 4$4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 Description of the test cases follows.

The only line for each test case contains a single integer 𝑛$n$ (1≤𝑛≤105$1\le n\le {10}^5$).

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 105${10}^5$.

Output

For each test case print 𝑛$n$ integers 𝑝1$p_1$, 𝑝2$p_2$, …$\dots$, 𝑝𝑛$p_n$ — the permutation with the maximum possible value of lcm(1,𝑝1)+lcm(2,𝑝2)+…+lcm(𝑛,𝑝𝑛)$\mathrm{lcm}(1,p_1)+\mathrm{lcm}(2,p_2)+\dots +\mathrm{lcm}(n,p_n)$.

If there are multiple answers, print any of them.