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: MEDIUM
Tags: Matrices

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	x = int(input())
	y = []
	for n in range(x):
		l = list(map(int, input().split()))
		y.append(l)
	c = 0
	i = 0
	direct = 0 if y[0][1] == 2 else 1
	while i < x - 1:
		i += 1
		if direct == 0 and y[0][i] == i + 1 or (direct == 1 and y[i][0] == i + 1):
			continue
		direct = 0 if direct else 1
		c += 1
	if direct:
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	matrix = []
	for i in range(n):
		li = list(map(int, input().split()))
		matrix.append(li)
	li = matrix[0]
	boolean = ['True'] * n
	count = 0
	for j in range(n):
		if li[j] != j + 1:
			boolean[j] = 'False'
	for k in range(n - 1, 0, -1):
		if boolean[k] == 'True':
			continue
		for i in range(k, 0, -1):
			if boolean[i] == 'True':
				boolean[i] = 'False'
			else:
				boolean[i] = 'True'
		count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(n):
		r = list(map(int, input().split()))
		l.append(r)
	ans = 0
	for k in range(n - 1, 0, -1):
		if l[0][k] != k + 1 and ans % 2 == 0:
			ans += 1
		if l[0][k] == k + 1 and ans & 1:
			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)


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)


for _ in range(int(input())):
	N = int(input())
	req = 0
	prev = True
	for (i, s) in enumerate(input().split()[1:] + [str(N + 1)], 2):
		if i == 2:
			prev = int(s) == i
		elif (int(s) == i) != prev:
			prev = not prev
			req += 1
	for _ in range(N - 1):
		input()
	print(req)


for _ in range(int(input())):
	n = int(input())
	matrix = []
	for i in range(n):
		matrix.append([int(x) for x in input().split()])
	cur = 0
	a = []
	for i in range(n):
		if matrix[i][0] == n * i + 1:
			a.append(0)
		else:
			a.append(1)
	a = a[::-1]
	s = 0
	cur = 0
	for i in range(len(a) - 1):
		if a[i] != cur:
			cur = a[i]
			s += 1
	print(s)


def rightmostF(row):
	for i in range(len(row) - 1, -1, -1):
		if row[i] is False:
			return i
	return -1
T = int(input())
for _ in range(T):
	N = int(input())
	mat = []
	rowBool = []
	count = 0
	for i in range(N):
		row = list(map(int, input().split()))
		mat.append(row)
	for i in range(N):
		rowBool.append(mat[0][i] == i + 1)
	while True:
		rightmostFalse = rightmostF(rowBool)
		if rightmostFalse == -1:
			break
		count = count + 1
		for i in range(1, rightmostFalse + 1):
			rowBool[i] = not rowBool[i]
	print(count)


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


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)


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


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
		elif matrix[i][0] != i * n + 1:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	emp = []
	count = 0
	for i in range(n):
		emp.append(list(map(int, input().split())))
	while n > 1:
		if emp[0][n - 1] != n:
			count += 1
			for i in range(n):
				for k in range(i + 1, n):
					(emp[i][k], emp[k][i]) = (emp[k][i], emp[i][k])
		n -= 1
	print(count)


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
	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)


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())
	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)


t = int(input())
while t > 0:
	m = []
	ms = int(input())
	for i in range(ms):
		mrow = list(map(int, input().split()))
		m.append(mrow)
	step = 0
	for i in range(ms - 1, 0, -1):
		current = m[i][i - 1] + 1
		if current == m[i][i]:
			continue
		else:
			step += 1
			for j in range(i + 1):
				for k in range(j, i + 1):
					temp = m[j][k]
					m[j][k] = m[k][j]
					m[k][j] = temp
	t -= 1
	print(step)


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


for _ in range(int(input())):
	N = int(input())
	arr = [None] * N
	arr[0] = 0
	for i in range(N):
		x = list(map(int, input().split()))
		if i == 0:
			continue
		if x[i] - x[i - 1] == 1:
			arr[i] = 0
		else:
			arr[i] = 1
	ans = 0
	for i in range(1, len(arr) - 1):
		if arr[i] != arr[i + 1]:
			ans += 1
	if arr[-1] == 1:
		ans += 1
	print(ans)


def solve():
	for _ in range(int(input())):
		n = int(input())
		mat = [list(map(int, input().split())) for _ in range(n)]
		ans = 0
		for i in range(n - 1, 0, -1):
			if mat[i][i - 1] + 1 != mat[i][i]:
				ans += 1
				for j in range(i + 1):
					for k in range(j, i + 1):
						(mat[j][k], mat[k][j]) = (mat[k][j], mat[j][k])
		print(ans)
solve()


for _ in range(int(input())):
	n = int(input())
	m = []
	for i in range(n):
		j = [int(j) for j in input().split()]
		m.append(j)
	bool1 = []
	o = 1
	for k in m[0]:
		if k == o:
			bool1.append(True)
		else:
			bool1.append(False)
		o += 1
	count = 0
	for k in range(-1, -(len(bool1) + 1), -1):
		if bool1[k] == False:
			for l in range(k, -len(bool1), -1):
				if bool1[l] == False:
					bool1[l] = True
				else:
					bool1[l] = False
			count += 1
		else:
			pass
	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)
	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


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


t = int(input())
for _ in range(t):
	n = int(input())
	temp = []
	for i in range(n):
		temp1 = [int(x) for x in input().split()]
		temp.append(temp1)
	count = 0
	while n > 1:
		if temp[0][n - 1] != n:
			count += 1
			for i in range(1, n):
				(temp[0][i], temp[i][0]) = (temp[i][0], temp[0][i])
		n = n - 1
	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)


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)


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		matrix = []
		for i in range(N):
			matrix.append(list(map(int, input().split())))
		print(solve(matrix))

def solve(matrix):
	N = len(matrix)
	count = 0
	for i in range(N - 1, 0, -1):
		if matrix[i][i] != matrix[i][i - 1] + 1:
			count += 1
			for j in range(i + 1):
				for k in range(j, i + 1):
					(matrix[j][k], matrix[k][j]) = (matrix[k][j], matrix[j][k])
	return count
main()


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)
		elif j > 0:
			j -= 1
		else:
			i -= 1
	print(counter)


t = int(input())
for x in range(t):
	n = int(input())
	x = []
	y = 0
	for i in range(n):
		x.append(list(map(int, input().split())))
	while n > 1:
		if x[0][n - 1] != n:
			y += 1
			for i in range(1, n):
				(x[0][i], x[i][0]) = (x[i][0], x[0][i])
		n -= 1
	print(y)


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


try:
	t = int(input())
	while t > 0:
		m = []
		ms = int(input())
		for i in range(ms):
			mrow = list(map(int, input().split()))
			m.append(mrow)
		step = 0
		for i in range(ms - 1, 0, -1):
			current = m[i][i - 1] + 1
			if current == m[i][i]:
				continue
			else:
				step = step + 1
				for j in range(i + 1):
					for k in range(j, i + 1):
						temp = m[j][k]
						m[j][k] = m[k][j]
						m[k][j] = temp
		t = t - 1
		print(step)
except EOFError as e:
	print(e)


def boolArr(arr, n):
	barr = [True if arr[0][i] == i + 1 else False for i in range(n)]
	return barr

def transpose(arr, n):
	for i in range(n):
		for j in range(n):
			if j > i:
				(arr[i][j], arr[j][i]) = (arr[j][i], arr[i][j])
	return arr
for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	barr = boolArr(arr, n)
	count = 0
	for i in range(n - 1, -1, -1):
		if not barr[i]:
			arr = transpose(arr, i + 1)
			barr = boolArr(arr, n)
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	list2 = []
	list_v = []
	list_h = []
	for i in range(n):
		list1 = list(map(int, input().split()))
		list2.append(list1)
	list_h = list2[0]
	for z in list2:
		list_v.append(z[0])
	j = 0
	serial = 1
	count = 0
	switch = 'h'
	while j < n:
		if switch == 'h':
			if list_h[j] != serial:
				switch = 'v'
				count += 1
		elif list_v[j] != serial:
			switch = 'h'
			count += 1
		serial += 1
		j += 1
	if list_h[n - 1] != n:
		count += 1
	if list_h[1] == 2:
		print(count)
	else:
		print(count - 1)


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:
	mm = []
	mms = int(input())
	for i in range(mms):
		mrow = list(map(int, input().split()))
		mm.append(mrow)
	c = 0
	for i in range(mms - 1, 0, -1):
		current = mm[i][i - 1] + 1
		if current == mm[i][i]:
			continue
		else:
			c = c + 1
			for j in range(i + 1):
				for k in range(j, i + 1):
					my_temp = mm[j][k]
					mm[j][k] = mm[k][j]
					mm[k][j] = my_temp
	t = t - 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		s = list(map(int, input().split()))
		l.append(s)
	a = l[0]
	a.append(n + 1)
	c = 0
	for i in range(1, n):
		if a[i] == i + 1 and a[i + 1] == i + 2 or (a[i] == i * n + 1 and a[i + 1] == (i + 1) * n + 1):
			continue
		else:
			c += 1
	print(c)


t = int(input())

def fun(ar):
	far = 0
	xv = 1
	for i in range(len(ar) - 1):
		if ar[i] == xv:
			continue
		else:
			xv = ar[i]
			far += 1
	return far
for _ in range(t):
	n = int(input())
	val = [*range(1, n * n + 1, n)]
	ar = []
	far = []
	for i in range(n):
		xa = list(map(int, input().split()))
		ar.append(xa)
		if xa[0] == val[i]:
			far.append(1)
		else:
			far.append(0)
	far = far[::-1]
	v = fun(far)
	print(v)


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


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


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list((int(ele) for ele in input().strip().split()))[:n])
	p = 0
	for i in range(n - 1, 0, -1):
		if l[0][i] != i + 1 and p % 2 == 0:
			p += 1
		if l[0][i] == i + 1 and p & 1:
			p += 1
	print(p)


import sys
import math
import bisect
import numpy as np
from sys import stdin, stdout
from itertools import accumulate, chain, combinations, groupby, permutations, product
from collections import deque, Counter
from bisect import bisect_left, bisect_right
from math import gcd, sqrt, sin, cos, tan, degrees, radians
from fractions import Fraction
from decimal import Decimal
import sys
MOD = 10 ** 9 + 7
INF = 10 ** 20
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def solve():
	n = int(input())
	q = []
	for i in range(n):
		q.append(list(map(int, input().split())))
	r = 0
	while n > 1:
		if q[0][n - 1] != n:
			r += 1
			for i in range(n):
				(q[0][i], q[i][0]) = (q[i][0], q[0][i])
		n -= 1
	print(r)
for _ in range(int(input())):
	solve()


from collections import Counter, UserString
mod = lambda n: n % (10 ** 9 + 7)
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n):
	print(mod(n))

def yn(b, caps=False):
	if b:
		returning = 'Yes'
	else:
		returning = 'No'
	if caps:
		return returning.upper()
	return returning

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def decimal(n):
	return int(ans) + int(int(ans) != ans)

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	n = ii()
	l = []
	for i in r2(n):
		l.append(li())
	c = 0
	p = n
	for i in range(n - 1, 0, -1):
		if l[0][i] != i + 1:
			c += 1
			for j in r2(i):
				(l[0][j], l[j][0]) = (l[j][0], l[0][j])
	print(c)


tests = int(input())
for i in range(tests):
	n = int(input())
	mat = []
	for j in range(n):
		row = list(map(int, input().split()))
		mat.append(row)
	ans = 0
	for j in range(n - 1, 0, -1):
		if mat[0][j] != j + 1 and ans % 2 == 0:
			ans += 1
		if mat[0][j] == j + 1 and ans & 1:
			ans += 1
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		grid = []
		for _ in range(n):
			grid.append(list(map(int, input().split())))
		ans = 0
		for i in range(n - 1, -1, -1):
			if grid[0][i] != i + 1:
				for j in range(0, i):
					(grid[j][0], grid[0][j]) = (grid[0][j], grid[j][0])
				ans += 1
		print(ans)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split()))) if i == 0 else input()
	ans = 0
	flag = 0
	for i in range(n - 1, 0, -1):
		if flag == 0 and a[0][i] != i + 1:
			ans += 1
			flag = 1
		elif flag == 1 and a[0][i] == i + 1:
			ans += 1
			flag = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [list(map(int, input().split())) for _ in range(n)]
	b = [False] * n
	for i in range(n):
		if l[0][i] == i + 1:
			b[i] = True
	count = 0
	for i in range(n - 1, 0, -1):
		if b[i] == True:
			continue
		else:
			count += 1
			for j in range(i, 0, -1):
				b[j] = False if b[j] else True
	print(count)


def transpose(arr, n):
	for i in range(n):
		for j in range(n):
			if j > i:
				(arr[i][j], arr[j][i]) = (arr[j][i], arr[i][j])
	return arr

def update(arr, n):
	row = [True if arr[0][i] == i + 1 else False for i in range(n)]
	return row
for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	row = update(arr, n)
	moves = 0
	for i in range(n - 1, -1, -1):
		if not row[i]:
			arr = transpose(arr, i + 1)
			row = update(arr, n)
			moves += 1
	print(moves)


t = int(input())
for ii in range(t):
	n = int(input())
	L = []
	for x in range(n):
		l = list(map(int, input().split()))
		L.append(l)
	c = 0
	i = 0
	direct = 0 if L[0][1] == 2 else 1
	while i < n - 1:
		i += 1
		if direct == 0 and L[0][i] == i + 1 or (direct == 1 and L[i][0] == i + 1):
			continue
		direct = 0 if direct else 1
		c += 1
	if direct:
		c += 1
	print(c)


for m in range(int(input())):
	p = int(input())
	a = []
	c = 0
	for i in range(p):
		a.append(list(map(int, input().split())))
	while p > 1:
		if a[0][p - 1] != p:
			c += 1
			for i in range(1, p):
				(a[0][i], a[i][0]) = (a[i][0], a[0][i])
		p -= 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		if not i:
			acc = list(map(int, input().split()))
			bel = [acc[0]]
		else:
			bel.append(list(map(int, input().split()))[0])
	cnt = 0
	for i in range(n - 1, -1, -1):
		if acc[i] > bel[i]:
			(acc[:i + 1], bel[:i + 1]) = (bel[:i + 1], acc[:i + 1])
			cnt += 1
	print(cnt)