A permutation of length n is an array of size n consisting of n distinct integers in the range [1, n]. For example, (3, 2, 4, 1) is a permutation of length 4, but (3, 3, 1, 4) and (2, 3, 4, 5) are not, as (3, 3, 1, 4) contains duplicate elements, and (2, 3, 4, 5) contains elements not in range [1,4].
A permutation p of length n is good if and only if for any 1 ≤ i ≤ n, pi ≠ i.
Please find the lexicographically smallest good permutation p.
Definition for "lexicographically smaller":
For two permutations p and q, we say that p is lexicographically smaller than q if and only if there exists a index 1 ≤ l ≤ n such that:
- For any 1 ≤ i < l, pi = qi. Note that if l = 1, this constraint means nothing.
- and, pl < ql.

For example, (2, 3, 1, 4) < (2, 3, 4, 1) < (3, 4, 1, 2). The lexicographically smallest permutation is, of course, (1, 2, ..., n), though this one is not good.

-----Input-----
First line of the input contains an integer T denoting number of test cases.
For each test case, the only line contains an integer n.

-----Output-----
For each test case, output the lexicographically smallest good permutation of length n. It's guaranteed that this permutation exists.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 105

-----Subtasks-----
- Subtask #1 (17 points): 2 ≤ n ≤ 9
- Subtask #2 (83 points): Original Constraints

-----Example-----
Input:
4
2
3
5
6

Output:
2 1
2 3 1
2 1 4 5 3
2 1 4 3 6 5

-----Explanation-----
Example case 1. The only good permutation of length 2 is (2, 1).
Example case 2. Consider all permutations of length 3, they are(in lexicographically order):
- p = (1, 2, 3), it's not good since p[1] = 1, p[2] = 2 and p[3] = 3;
- p = (1, 3, 2), it's not good since p[1] = 1;
- p = (2, 1, 3), it's not good since p[3] = 3;
- p = (2, 3, 1), it's good since p[1] ≠ 1, p[2] ≠ 2 and p[3] ≠ 3;
- p = (3, 1, 2), it's good since p[1] ≠ 1, p[2] ≠ 2 and p[3] ≠ 3;
- p = (3, 2, 1), it's not good since p[2] = 2.
Thus the minimum good one is (2, 3, 1).
Example case 3. Consider two good permutations for third test case: p=(2, 1, 4, 5, 3) and q=(2, 4, 1, 5, 3), then p < q. You can check lexicographically condition as follows. Find the first index where the entries of two permutations are different, and compare those entries. For example, in this case, the first position where the entries differ is index 2. You can see that p[2] < q[2], as 1 < 4, so p is lexicographically smaller than q.

Difficulty: interview

Starter code:

Solutions:
tests = int(input())
for t in range(tests):
  n = int(input())
  permut='2'
  permut_list=[]
  if n%2==0:
    for i in range(2, n+1):
      if i%2==1:
        permut=permut+' '+str(i+1)
      else:
        permut=permut+' '+str(i-1)
    print(permut)
    pass
  elif n==1:
    print(1)
    pass
  else:
    for i in range(2, n):
      if i%2==1:
        permut_list.append(str(i+1))
      else:
        permut_list.append(str(i-1))
    permut_list.pop(-1)
    permut_list.append(str(n))
    permut_list.append(str(n-2))
    this_permut='2'
    for el in permut_list:
      this_permut=this_permut+' '+el
    print(this_permut)

tests = int(input())
for t in range(tests):
  n = int(input())
  permut='2'
  permut_list=[]
  if n%2==0:
    for i in range(2, n+1):
      if i%2==1:
        permut=permut+' '+str(i+1)
      else:
        permut=permut+' '+str(i-1)
    print(permut)
    pass
  elif n==1:
    print(1)
    pass
  else:
    for i in range(2, n):
      if i%2==1:
        permut_list.append(str(i+1))
      else:
        permut_list.append(str(i-1))
    permut_list.pop(-1)
    permut_list.append(str(n))
    permut_list.append(str(n-2))
    this_permut='2'
    for el in permut_list:
      this_permut=this_permut+' '+el
    print(this_permut)

tests = int(input())
for t in range(tests):
  n = int(input())
  permut='2'
  if n%2==0:
    for i in range(2, n+1):
      if i%2==1:
        permut=permut+' '+str(i+1)
      else:
        permut=permut+' '+str(i-1)
    print(permut)
    pass
  elif n==1:
    print(1)
    pass
  else:
    for i in range(2, n):
      if i%2==1:
        permut=permut+' '+str(i+1)
      else:
        permut=permut+' '+str(i-1)
    edit_permut = permut[:-1]
    temp=permut[-1]
    edit_permut=edit_permut+str(n)
    edit_permut=edit_permut+' '+temp
    print(edit_permut)
    pass

# cook your dish here
try:
    for _ in range(int(input())):
        N = int(input())
        odd = False
        
        li = [0] * N
        
        if N & 1 == 1:
            odd = True
            N -= 3
            
        for i in range(0, N, 2):
            li[i] = i + 2
            li[i + 1] = i + 1
            
        if odd:
            li[N] = N + 2
            li[N + 1] = N + 3
            li[N + 2] = N + 1
            
        print(*li)
            
        
    
except Exception as e:
    print(e.__class__)

for _ in range(int(input())):
    n=int(input())
    l=[i for i in range(1,n+1)]
    for i in range(n):
        if l[i]==i+1:
            try:
                l[i],l[i+1]=l[i+1],l[i]
            except:
                l[i],l[i-1]=l[i-1],l[i]
    for item in l:
        print(item,end=" ")
    print()

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    if n<=3:
        l=[i for i in range(2,n+1)]
        l=l+[1]
        print(*l)
    elif n==4:
        print(2,1,4,3)
    elif n==5:
        print(2,1,4,5,3)
    else:
        l=[i for i in range(1,n+1)]
        if n%2==0:
            for i in range(0,n,2):
                l[i],l[i+1]=l[i+1],l[i]
            print(*l)
        else:
            for i in range(0,n-4,2):
                l[i],l[i+1]=l[i+1],l[i]
            l[-3],l[-2],l[-1]=l[-2],l[-1],l[-3]
            print(*l)
                
            


# cook your dish here
for _ in range(int(input())):
    n=int(input())
    if n%2==0:
        for i in range(1,n+1):
            if i%2==0:
                print(i-1,end=" ")
            else:
                print(i+1,end=" ")
    else:
        for j in range(1,n-1):
            if j%2==0:
                print(j-1,end=" ")
            else:
                print(j+1,end=" ")
        print(n,end=" ")
        print(n-2,end=" ")
    print()
    

            

try:
    t = int(input())
    for _ in range(t):
        n = int(input())
        odd = 0
        if n&1:
            odd=1 
            n-=3
        arr = []
        for i in range(1,n+1,2):
            arr.append(i+1)
            arr.append(i)
        if odd:
            arr.append(n+2)
            arr.append(n+3)
            arr.append(n+1)
        for i in arr:
            print(i,end = ' ')
        print()
        
except:
    pass
                


try:
    t = int(input())
    for _ in range(t):
        n = int(input())
        odd = 0
        if n&1:
            odd=1 
            n-=3
        arr = []
        for i in range(1,n+1,2):
            arr.append(i+1)
            arr.append(i)
        if odd:
            arr.append(n+2)
            arr.append(n+3)
            arr.append(n+1)
        for i in arr:
            print(i,end = ' ')
        print()
        
except:
    pass
                


# cook your dish here
try:
    T=int(input())
    ans=[]
    for _ in range(T):
        n=int(input())
        a=[0]*n
        for i in range(0,n,2):
            a[i]=i+2
            if i==n-1:
                a[i]=a[i-1]
                a[i-1]=i+1
            else:
                a[i+1]=i+1
                
        ans.append(a)
    for _ in range(T):
        print(' '.join(map(str,ans[_])))
except EOFError:            
    pass

# cook your dish here
try:
    T=int(input())
    while T>0 :
        n=int(input())
        i=1 
        for j in range(n//2-1) :
            print(i+1,i,end=" ")
            i+=2 
        if n%2==0 :
            print(i+1,i)
        else :
            print(i+1,i+2,i)
        T-=1
except:
    pass

import sys
import math

def main(n):

    arr=[]
    for i in range(1,n+1):
        arr.append(i)
    i=0 
    j=1 
    
    while i<n and j<n:
        arr[i],arr[j]=arr[j],arr[i]
        i+=2
        j+=2 
    
    if n&1:
        arr[-2],arr[-1]=arr[-1],arr[-2]
    print(*arr)
    return 
for _ in range(int(input())):
    n=int(input())
    main(n)

    
        

        


T = int(input())

while (T > 0):
    T-=1 
    k = int(input())
    perm = []
    if k % 2 == 0:
        for i in range(2,k+1,2):
            perm.append(i)
            perm.append(i-1)
    else:
        r = k - 3
        for i in range(2,k-2,2):
            perm.append(i)
            perm.append(i-1)
        perm.extend( [k-1,k,k-2] )
    for i in perm:
        print(i,end=' ')
    print()
        


# cook your dish here
for _ in range(int(input())):
    
    n=int(input())
    
    if n%2==0:
        
        ans=[]
        for i in range(1,n+1,2):
            ans.append(i+1)
            ans.append(i)
            
    else:
        
        ans=[]
        
        for i in range(1,n+1-3,2):
            ans.append(i+1)
            ans.append(i)
            
        ans.extend([n-1,n,n-2])
        
    print(*ans)


# cook your dish here
t = int(input())
for _ in range(t):
    n = int(input())
    l=[]
    if n%2==0:
        for i in range(1,n+1,2):
            print(i+1,end=' ')
            print(i,end=' ')
        print()
    else:
        for i in range(1,n-2,2):
            print(i+1,end=' ')
            print(i,end=' ')
        print(n-1,n,n-2)

from sys import stdin

try:
    t = eval(stdin.readline())
    for _ in range(t):
        n = eval(stdin.readline())
        arr = [x for x in range(1, n+1)]
        
        if n % 2 == 0:
            for i in range(0, n-1, 2):
                arr[i], arr[i+1] = arr[i+1], arr[i]
        else:
            for i in range(0, n, 2):
                if i < n-2:
                    arr[i], arr[i+1] = arr[i+1], arr[i]
                else:
                    arr[i], arr[i-1] = arr[i-1], arr[i]        
        
        print(' '.join(list(map(str, arr))))
except: pass

# cook your dish here
for _ in range(int(input())):
    n = int(input())
    if n%2: l = list(range(1,n))
    else:   l = list(range(1,n+1))
    for i in range(0,len(l),2):
        l[i], l[i+1] = l[i+1], l[i]
    if n%2:
        l.append(n)
        l[n-2],l[n-1] = l[n-1], l[n-2]
    for i in l:
        print(i, end = " ")
    print()

# cook your dish here
t=int(input())
for _ in range(t):
    n=int(input())
    lis=[int(i) for i in range(n)]
    if n%2==0:
        for i in range(n):
            if i%2==0:
                lis[i]=i+2
            else:
                lis[i]=i
    else:
        for i in range(n-3):
            if i%2==0:
                lis[i]=i+2
            else:
                lis[i]=i
        lis[n-3],lis[n-2],lis[n-1]=n-1,n,n-2
    for ele in lis:
        print(ele,end=' ')
        
    print('\n')
            
                

# cook your dish here
try:
    for _ in range(int(input())):
        n=int(input())
        l=[]
        if (n%2==0):
            for i in range(1,n+1):
                if(i%2==0):
                    l.append(str(i-1))
                else:
                    l.append(str(i+1))
        else:
            for j in range(1,n-1):
                if(j%2==0):
                    l.append(str(j-1))
                else:
                    l.append(str(j+1))
            l.append(str(n))
            l.append(str(n-2))
        print(' '.join(l))
except:
    pass



# cook your dish here
for _ in range(int(input())):
    n = int(input())
    if n == 2:
        print(*[2,1])
    elif n == 3:
        print(*[2,3,1])
    else:
        arr = list(range(1,n+1))
        for i in range(1,n,2):
            if n%2 == 1 and n-i == 2:
                arr[i-1], arr[i], arr[i+1] = arr[i], arr[i+1], arr[i-1]
                break
            else:
                arr[i], arr[i-1] = arr[i-1], arr[i]
        print(*arr)
                





for _ in range(int(input())):

    n=int(input())
    #w=[int(x) for x in input().split()]
    a=list(range(1,n+1))
    if n%2==0:
      for i in range(0,n,2):
         a[i],a[i+1]=a[i+1],a[i]
    else:
       
       for i in range(0,n-1,2):
          a[i],a[i+1]=a[i+1],a[i]
       
       a[-1],a[-2]=a[-2],a[-1] 

    for x in a:
    	print(x,end=" ")
    print()



t = int(input())
while t:
    n = int(input())
    if n%2 == 0:
        for i in range(2, n+1, 2):
            print(i, i-1, end = ' ')
    else:
        for i in range(2, n-2, +2):
            print(i, i-1, end = ' ')
        print(n-1, n, n-2, end = ' ')
    print()
    t = t - 1

for _ in range(int(input())):
    n=int(input())
    if n%2==0:
        ans=[]
        c=1
        while c<=n:
            ans.append(c+1)
            ans.append(c)
            c+=2
        print(*ans)
    else:
        aux=[n-1,n,n-2]
        ans=[]
        c=1
        while c<=(n-3):
            ans.append(c+1)
            ans.append(c)
            c+=2
        ans=ans+aux
        print(*ans)