Permutation solution codeforces – Recall that a permutation of length 𝑛n is an array where each element from 11 to 𝑛n occurs exactly once.
[Solution] Permutation solution codeforces
For a fixed positive integer 𝑑d, let’s define the cost of the permutation 𝑝p of length 𝑛n as the number of indices 𝑖i (1≤𝑖<𝑛)(1≤i<n) such that 𝑝𝑖⋅𝑑=𝑝𝑖+1pi⋅d=pi+1.
For example, if 𝑑=3d=3 and 𝑝=[5,2,6,7,1,3,4]p=[5,2,6,7,1,3,4], then the cost of such a permutation is 22, because 𝑝2⋅3=𝑝3p2⋅3=p3 and 𝑝5⋅3=𝑝6p5⋅3=p6.
Your task is the following one: for a given value 𝑛n, find the permutation of length 𝑛n and the value 𝑑d with maximum possible cost (over all ways to choose the permutation and 𝑑d). If there are multiple answers, then print any of them.
The first line contains a single integer 𝑡t (1≤𝑡≤5001≤t≤500) — the number of test cases.
The single line of each test case contains a single integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105).
The sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105.
[Solution] Permutation solution codeforces
For each test case, print the value 𝑑d in the first line, and 𝑛n integers in the second line — the permutation itself. If there are multiple answers, then print any of them.
2 2 3
2 1 2 3 2 1 3