[Solution] Permutation solution codeforces

Permutation solution codeforces – Recall that a permutation of length 𝑛n is an array where each element from 11 to 𝑛n occurs exactly once.

Table of Contents

[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 𝑝23=𝑝3p2⋅3=p3 and 𝑝53=𝑝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.

Input

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𝑛21052≤n≤2⋅105).

The sum of 𝑛n over all test cases does not exceed 21052⋅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.

Example
input

Copy
2
2
3
output

Copy
2
1 2
3
2 1 3

 

For Solution

Click Here

Leave a Comment