Chef Ada has a matrix with $N$ rows (numbered $1$ through $N$ from top to bottom) and $N$ columns (numbered $1$ through $N$ from left to right) containing all integers between $1$ and $N^2$ inclusive. For each valid $i$ and $j$, let's denote the cell in the $i$-th row and $j$-th column by $(i,j)$.
Ada wants to sort the matrix in row-major order ― for each valid $i$ and $j$, she wants the cell $(i, j)$ to contain the value $(i-1) \cdot N + j$.
In one operation, Ada should choose an integer $L$ and transpose the submatrix between rows $1$ and $L$ and columns $1$ and $L$ (inclusive). Formally, for each $i$ and $j$ ($1 \le i, j \le L$), the value in the cell $(i, j)$ after this operation is equal to the value in $(j, i)$ before it.
The initial state of the matrix is chosen in such a way that it is possible to sort it using a finite number of operations (possibly zero). Find the smallest number of operations required to sort the matrix.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The next $N$ lines describe the matrix. For each valid $i$, the $i$-th of these lines contains $N$ space-separated integers ― the initial values in cells $(i, 1), (i, 2), \ldots, (i, N)$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest number of operations required to sort the matrix.

-----Constraints-----
- $4 \le N \le 64$
- the sum of $N^2$ over all test files does not exceed $3 \cdot 10^5$

-----Subtasks-----
Subtask #1 (10 points):
- $T \le 50$
- $N = 4$
Subtask #2 (90 points): original constraints

-----Example Input-----
1
4
1 2 9 13
5 6 10 14
3 7 11 15
4 8 12 16

-----Example Output-----
2

-----Explanation-----
Example case 1: After the first operation, with $L = 2$, the resulting matrix is
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

After the second operation, with $L = 4$, the matrix becomes sorted
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 n=int(input())
 a=[]
 l=0
 for i in range(n):
  a.append(list(map(int,input().split())))
 for i in range(n-1,0,-1):
  r=a[i][i-1]+1
  if a[i][i]!=r:
   l+=1
   n=i+1
   for j in range(n):
    for k in range(j,n):
     a[j][k],a[k][j]=a[k][j],a[j][k]
    
 print(l)


for _ in range(int(input())):
 n=int(input())
 a=[]
 l=0
 for i in range(n):
  a.append(list(map(int,input().split())))
 for i in range(n-1,0,-1):
  r=a[i][i-1]+1
  if a[i][i]!=r:
   l+=1
   n=i+1
   for j in range(n):
    for k in range(j,n):
     a[j][k],a[k][j]=a[k][j],a[j][k]
    
 print(l)
 


# cook your dish here
for i in range(int(input())):
 n = int(input())
 mat = []
 for i in range(n):
  mat.append([int(j) for j in input().split()])
 # print(mat)
 ans = 0
 t = True
 for i in range(n-1, 0, -1):
  if t:
   if mat[0][i] != i+1:
    t = False
    ans += 1
  else:
   if mat[0][i] == i+1:
    t = True
    ans += 1
 print(ans)

t=int(input())
while(t>0):
 t-=1
 aa=int(input())
 count=0
 blist=[]
 for i in range(aa):
  blist.append([int(x) for x in input().split()])
 for d in range(aa-1,0,-1):
  result=blist[d][d-1]+1
  if result!=blist[d][d]:
   count+=1
   next=d+1
   for i in range(next):
    for j in range(i,next):
     temp=blist[i][j]
     blist[i][j]=blist[j][i]
     blist[j][i]=temp
 print(count)

# cook your dish here
for _ in range(int(input())):
 n = int(input())
 mat = [list(map(int, input().strip().split()))
   for i in range(n)]
 ans = 0
 equal = True
 for i in range(n-1, 0, -1):
  if equal and mat[0][i] != i+1:
   ans += 1
   equal = False
  elif not equal and mat[0][i] == i+1:
   ans += 1
   equal = True
 print(ans)



t=int(input())
while(t>0):
 t-=1
 pp=int(input())
 count=0;blist=[]
 for i in range(pp):
  blist.append([int(x) for x in input().split()])
 for d in range(pp-1,0,-1):
  done=blist[d][d-1]+1
  if done!=blist[d][d]:
   count+=1
   don=d+1
   for i in range(don):
    for j in range(i,don):
     trav=blist[i][j]
     blist[i][j]=blist[j][i]
     blist[j][i]=trav
 print(count)

t=int(input())
while t>0:
 n=int(input())
 mat=[]
 for i in range(n):
  l=[int(x) for x in input().split()]
  mat.append(l)
 #print(mat)
 c=0 
 for i in range(n-1,-1,-1):
  if(mat[0][i]!=i+1):
   c+=1
   for j in range(i+1):
    mat[0][j],mat[j][0]=mat[j][0],mat[0][j]
 print(c)
 t-=1

t=int(input())
while t>0:
 n=int(input())
 mat=[]
 for i in range(n):
  l=[int(x) for x in input().split()]
  mat.append(l)
 #print(mat)
 c=0 
 for i in range(n-1,-1,-1):
  if(mat[0][i]!=i+1):
   c+=1
   for j in range(i+1):
    mat[0][j],mat[j][0]=mat[j][0],mat[0][j]
 print(c)
 t-=1

t=int(input())
while t>0:
 n=int(input())
 mat=[]
 for i in range(n):
  l=[int(x) for x in input().split()]
  mat.append(l)
 #print(mat)
 c=0 
 for i in range(n-1,-1,-1):
  if(mat[0][i]!=i+1):
   c+=1
   for j in range(i+1):
    mat[0][j],mat[j][0]=mat[j][0],mat[0][j]
 print(c)
 t-=1

t=int(input())
while t>0:
 n=int(input())
 mat=[]
 for i in range(n):
  l=[int(x) for x in input().split()]
  mat.append(l)
 #print(mat)
 c=0 
 for i in range(n-1,-1,-1):
  if(mat[0][i]!=i+1):
   c+=1
   for j in range(i+1):
    mat[0][j],mat[j][0]=mat[j][0],mat[0][j]
 print(c)
 t-=1

# cook your dish here
def check_For_L(i,n,counter):
 if counter&1: 
  if matrix[0][i]!=i*n+1:
   return False
 elif matrix[i][0]!=i*n+1:
  return False
 return True
T=int(input())
for _ in range(T):
 N=int(input())
 matrix=[]
 for j in range(N):
  matrix.append(list(map(int,input().split())))
 counter=0
 
 for j in reversed(list(range(N))):
  if check_For_L(j,N,counter):
   continue
  else:
   counter+=1
 
 print(counter)


for _ in range(int(input())):
 n=int(input())
 matrix=[]
 for i in range(n):
  matrix.append(list(map(int,input().split())))
 count=0
 for i in reversed(list(range(n))):
  if count&1:
   if matrix[0][i] != i*n+1:
    count+=1
  else:
   if matrix[i][0] != i*n+1:
    count+=1 
 print(count)
   
   


# cook your dish here
t=int(input())
while(t>0):
 t-=1
 pp=int(input())
 count=0
 blist=[]
 for i in range(pp):
  blist.append([int(x) for x in input().split()])
 for d in range(pp-1,0,-1):
  done=blist[d][d-1]+1
  if done!=blist[d][d]:
   count+=1
   don=d+1
   for i in range(don):
    for j in range(i,don):
     trav=blist[i][j]
     blist[i][j]=blist[j][i]
     blist[j][i]=trav
 print(count)

# cook your dish here
t = int(input())
while (t > 0):
 t -= 1
 n = int(input())
 count = 0
 list = []
 for i in range (n):
  list.append([int(x) for x in input().split()])
 for d in range(n - 1, 0, -1):
  result = list[d][d - 1] + 1
  if result != list[d][d]:
   count += 1
   next = d + 1
   for i in range (next):
    for j in range(i, next):
     temp = list[i][j]
     list[i][j] = list[j][i]
     list[j][i] = temp
 print(count)

# cook your dish here
import sys

t=int(input().strip())
for _ in range(t):
 n=int(input().strip())
 array=[]
 for i in range(n):
  lista=[]
  lista[:]=map(int,input().strip().split())
  array.append(lista)
 j=n-1
 i=0
 counter=0
 for _ in range(n):
  if array[i][j]!=i+j+1:
   counter+=1
   if j>0:
    j-=1 
   else:
    i-=1 
   i, j= j, i
  else:
   if j>0:
    j-=1 
   else:
    i-=1
 print(counter)

# cook your dish here
t = int(input())
for i in range(t):
 n = int(input())
 mat =[]
 for j in range(0, n):
  a = list(map(int, input().split()))
  mat.append(a)
 count, flag = 0,0
 for j in range(1, n+1):
  if flag == 0:
   if mat[0][n-j]!=(n-j+1):
    count += 1 
    flag += 1 
  if flag == 1:
   if mat[n-j][0]!=(n-j+1):
    count+=1 
    flag=0 
 print(count)

# cook your dish here
t=int(input())
while(t>0):
 n=int(input())
 matrix=[]
 for i in range(n):
  a = list(map(int,input().split()))
  matrix.append(a)
 bool=[False for i in range(n)]
 for i in range(n):
  if matrix[0][i]==i+1:
   bool[i]=True
 count=0
 k=n-1
 while(k>=1):
  if bool[k]==False:
   count+=1
   for i in range(k+1):
    for j in range(i,k+1):
     matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] 
   for i in range(n):
    if matrix[0][i]==i+1:
     bool[i]=True
    else:
     bool[i]=False
  k-=1
 print(count)
 t-=1

# cook your dish here
t= int(input())
for test in range(t):
 n= int(input())
 matrix = []
 count = 0
 for i in range(n):
  A = list(map(int,input().split()))
  matrix.append(A)
 
 for i in range(n-1,0,-1):
  if matrix[0][i] != i+1:
   count+=1
   for j in range(i,0,-1):
    temp = matrix[0][j]
    matrix[0][j] = matrix[j][0]
    matrix[j][0] = temp
  
 
 print(count)


# cook your dish here
t = int(input())
for i in range(t):
 n = int(input())
 mat =[]
 for j in range(0, n):
  a = list(map(int, input().split()))
  mat.append(a)
 count, flag = 0,0
 for j in range(1, n+1):
  if flag == 0:
   if mat[0][n-j]!=(n-j+1):
    count += 1 
    flag += 1 
  if flag == 1:
   if mat[n-j][0]!=(n-j+1):
    count+=1 
    flag=0 
 print(count)

t = int(input())
while t>0:
 count=0
 n = int(input())
 l = []
 for i in range(n):
  l.append([int(x) for x in input().split()])
 for x in range(n-1,0,-1):
  r = l[x][x-1] + 1
  if r!=l[x][x]:
   count+=1; k = x + 1
   for i in range(k):
    for j in range(i,k):
     temp = l[i][j]
     l[i][j] = l[j][i]
     l[j][i] = temp
 t-=1
 print(count)

# cook your dish here
def transpose(lst, l):
 for i in range(l):
  for j in range(i,l):
   temp = lst[i][j]
   lst[i][j] = lst[j][i]
   lst[j][i] = temp

def printMatrix(lst):
 for i in lst:
  print(i)

# try:
t = int(input())
while t>0:
 n = int(input())
 lst = []
 bin = list()
 count = 0
 for i in range(n):
  lst.append(list(map(int, input().strip().split())))
 for j in reversed(range(1,n)):
  if not lst[0][j]==j+1:
   count += 1
   transpose(lst, j+1)
 if t==1:
  print(count, end=" ")
 else:
  print(count)

 t = t -1
# except:
#     pass






def transpose(lst, l):
 for i in range(l):
  for j in range(i,l):
   temp = lst[i][j]
   lst[i][j] = lst[j][i]
   lst[j][i] = temp

def printMatrix(lst):
 for i in lst:
  print(i)


t = int(input())
while t>0:
 n = int(input())
 lst = []
 bin = list()
 count = 0
 for i in range(n):
  lst.append(list(map(int, input().strip().split())))
 for j in reversed(range(1,n)):
  if not lst[0][j]==j+1:
   count += 1
   transpose(lst, j+1)
 if t==1:
  print(count, end=" ")
 else:
  print(count)

 t = t -1

t = int(input())
while (t > 0):
 t -= 1
 n = int(input())
 bits = [0] * n
 mat = []
 for i in range (n):
  mat.append([int(x) for x in input().split()])
 
 for j in range(n):
  if mat[0][j] != (j+1):
   bits[j] = 1
 ans = 0
 count = 0
 for i in range(n-1,0,-1):
  if bits[i] != count:
   ans += 1
   count = (count + 1)%2
 
 print(ans)
 


t = int(input())
while (t > 0):
 t -= 1
 n = int(input())
 count = 0
 list = []
 for i in range (n):
  list.append([int(x) for x in input().split()])
 for d in range(n - 1, 0, -1):
  result = list[d][d - 1] + 1
  if result != list[d][d]:
   count += 1
   next = d + 1
   for i in range (next):
    for j in range(i, next):
     temp = list[i][j]
     list[i][j] = list[j][i]
     list[j][i] = temp
 print(count)

t=int(input())
while(t>0):
 t-=1
 pp=int(input())
 count=0;blist=[]
 for i in range(pp):
  blist.append([int(x) for x in input().split()])
 for d in range(pp-1,0,-1):
  done=blist[d][d-1]+1
  if done!=blist[d][d]:
   count+=1
   don=d+1
   for i in range(don):
    for j in range(i,don):
     trav=blist[i][j]
     blist[i][j]=blist[j][i]
     blist[j][i]=trav
 print(count)