Prefix Permutation CodeChef Solution

Problem

You are given an integer $N$. Your task is to generate a permutation $P$ of size $N$, such that:

• For all $(1<i\le N)$, ∑�=1���∑j=1i​Pj​ is not divisible by $i$.
  In other words, the sum of prefix of length $i$ $(i>1)$ should not be divisible by $i$.

In case multiple such permutations exist, print any. If no such permutation exists, print $-1$ instead.

Note that a permutation of size $N$ contains all integers from $1$ to $N$ exactly once.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists a single integer $N$ — the size of the permutation.

Output Format

For each test case, output on a new line, $N$ space separated integers, denoting the required permutation.

In case multiple such permutations exist, print any. If no such permutation exists, print $-1$ instead.

Constraints

Sample 1:

3
4
6
7

3 4 1 2
1 2 4 6 3 5
-1

Explanation:

Test case $1$: A possible permutation satisfying the given conditions is $P=[3,4,1,2]$.

• For $i=2$: The prefix sum is $3+4=7$, which is not divisible by $2$.
• For $i=3$: The prefix sum is $3+4+1=8$, which is not divisible by $3$.
• For $i=4$: The prefix sum is $3+4+1+2=10$, which is not divisible by $4$.

Test case $2$: A possible permutation satisfying the given conditions is $P=[1,2,4,6,3,5]$.

• For $i=2$: The prefix sum is $1+2=3$, which is not divisible by $2$.
• For $i=3$: The prefix sum is $1+2+4=7$, which is not divisible by $3$.
• For $i=4$: The prefix sum is $1+2+4+6=13$, which is not divisible by $4$.
• For $i=5$: The prefix sum is $1+2+4+6+3=16$, which is not divisible by $5$.
• For $i=6$: The prefix sum is $1+2+4+6+3+5=21$, which is not divisible by $6$.

Test case $3$: It can be proven that no permutation of length $7$ satisfies the given conditions.