Sean invented a game involving a $2n\times2n$ matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times.  The goal of the game is to maximize the sum of the elements in the $n\times n$ submatrix located in the upper-left quadrant of the matrix.

Given the initial configurations for $\textit{q}$ matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix's upper-left quadrant is maximal.  

Example 

$matrix=[[1,2],[3,4]]$  

1 2
3 4

It is $2\times2$ and we want to maximize the top left quadrant, a $1\times1$ matrix.  Reverse row $1$:

1 2
4 3

And now reverse column $0$:

4 2
1 3

The maximal sum is $4$.

Function Description  

Complete the flippingMatrix function in the editor below.  

flippingMatrix has the following parameters: 

- int matrix[2n][2n]: a 2-dimensional array of integers  

Returns 

- int: the maximum sum possible.   

Input Format

The first line contains an integer $\textit{q}$, the number of queries.   

The next $\textit{q}$ sets of lines are in the following format:

The first line of each query contains an integer, $n$. 
Each of the next $2n$ lines contains $2n$ space-separated integers $matrix[i][j]$ in row $\boldsymbol{i}$ of the matrix.  

Constraints

$1\leq q\leq16$  
$1\leq n\leq128$  
$0\leq matrix[i][j]\leq4096$, where $0\leq i,j<2n$.

Sample Input
STDIN           Function
-----           --------
1               q = 1
2               n = 2
112 42 83 119   matrix = [[112, 42, 83, 119], [56, 125, 56, 49], \
56 125 56 49              [15, 78, 101, 43], [62, 98, 114, 108]]
15 78 101 43
62 98 114 108

Sample Output
414

Explanation

Start out with the following $2n\times2n$ matrix:

$matrix=\begin{bmatrix}112&42&83&119\\ 56&125&56&49\\ 15&78&101&43\\ 62&98&114&108\end{bmatrix}$

Perform the following operations to maximize the sum of the $n\times n$ submatrix in the upper-left quadrant:

Reverse column $2$ ($[83,56,101,114]\rightarrow[114,101,56,83]$), resulting in the matrix: 

$matrix=\begin{bmatrix}112&42&114&119\\ 56&125&101&49\\ 15&78&56&43\\ 62&98&83&108\end{bmatrix}$

Reverse row $0$ ($[112,42,114,119]\rightarrow[119,114,42,112]$), resulting in the matrix: 

$matrix=\begin{bmatrix}119&114&42&112\\ 56&125&101&49\\ 15&78&56&43\\ 62&98&83&108\end{bmatrix}$

The sum of values in the $n\times n$ submatrix in the upper-left quadrant is $119+114+56+125=414$.

Difficulty: MEDIUM
Tags: Constructive algorithms

Starter code:

Solutions:
q = int(input())
while q > 0:
	q -= 1
	n = int(input())
	A = []
	for i in range(2 * n):
		A += [list(map(int, input().split()))]
	ans = 0
	for i in range(n):
		for j in range(n):
			ans += max(A[i][j], A[2 * n - 1 - i][j], A[i][2 * n - 1 - j], A[2 * n - 1 - i][2 * n - 1 - j])
	print(ans)


q = int(input())
for _ in range(q):
	n = int(input())
	a = []
	for y in range(2 * n):
		a.append([int(x) for x in input().split()])
	suma = 0
	for i in range(n):
		for j in range(n):
			suma += max(max(a[i][j], a[2 * n - i - 1][j]), max(a[i][2 * n - j - 1], a[2 * n - i - 1][2 * n - j - 1]))
	print(suma)


import sys
q = int(input().strip())
for nq in range(q):
	n = int(input().strip())
	m = []
	for i in range(2 * n):
		m.append([int(x) for x in input().strip().split(' ')])
	_sum = 0
	for i in range(n):
		for j in range(n):
			_sum += max(m[i][j], m[2 * n - 1 - i][j], m[i][2 * n - 1 - j], m[2 * n - 1 - i][2 * n - 1 - j])
	print(_sum)


q = int(input())
for _ in range(q):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append([int(x) for x in input().strip().split()])
	val = 0
	for i in range(n):
		for j in range(n):
			m = 2 * n
			val += max([matrix[i][j], matrix[m - i - 1][j], matrix[m - i - 1][m - j - 1], matrix[i][m - j - 1]])
	print(val)


q = int(input())
for k in range(q):
	n = int(input())
	matrix = []
	for j in range(2 * n):
		row = list(map(int, input().strip().split(' ')))
		matrix.append(row)
	answer = 0
	for i in range(n):
		for j in range(n):
			ul = matrix[j][i]
			ur = matrix[j][2 * n - i - 1]
			ll = matrix[2 * n - j - 1][i]
			lr = matrix[2 * n - j - 1][2 * n - i - 1]
			answer += max(ul, ur, ll, lr)
	print(answer)


for _ in range(int(input())):
	n = int(input())
	mat = []
	for i in range(2 * n):
		mat.append(list(map(int, input().split())))
	ans = 0
	for i in range(n):
		for j in range(n):
			x = mat[i][j]
			x = max(x, mat[2 * n - 1 - i][j])
			x = max(x, mat[i][2 * n - 1 - j])
			x = max(x, mat[2 * n - 1 - i][2 * n - 1 - j])
			ans += x
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	mat = []
	for _ in range(2 * n):
		mat.append([int(i) for i in input().split()])
	ans = 0
	for i in range(n):
		for j in range(n):
			ans += max(mat[i][j], mat[2 * n - i - 1][j], mat[i][2 * n - j - 1], mat[2 * n - i - 1][2 * n - j - 1])
	print(ans)


def group(n, row, col):
	G = [[row, col]]
	G.append([row, 2 * n - 1 - col])
	G.append([2 * n - 1 - row, col])
	G.append([2 * n - 1 - row, 2 * n - 1 - col])
	return G

def solve(M, n):
	s = 0
	for row in range(0, n):
		for col in range(0, n):
			G = group(n, row, col)
			s += max((M[g[0]][g[1]] for g in G))
	return s

def solveProblem():
	n = int(input())
	M = []
	for i in range(2 * n):
		row = list(map(int, input().split()))
		M.append(row)
	s = solve(M, n)
	print(s)
T = int(input())
for t in range(T):
	solveProblem()


q = int(input().strip())
for k in range(q):
	n = int(input().strip())
	m = [[]] * (n * 2)
	s = 0
	for j in range(2 * n):
		m[j] = [int(i) for i in input().strip().split(' ')]
	for j in range(n):
		for i in range(n):
			ma = max(m[i][j], m[2 * n - i - 1][j], m[2 * n - i - 1][2 * n - j - 1], m[i][2 * n - j - 1])
			s += ma
	print(s)


def r():
	return list(map(int, input().split()))

def solve(M):
	n = len(M) // 2
	ans = 0
	for i in range(n):
		for j in range(n):
			ans += max(M[i][j], M[i][2 * n - 1 - j], M[2 * n - 1 - i][j], M[2 * n - 1 - i][2 * n - 1 - j])
	print(ans)

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		M = [r() for _ in range(2 * n)]
		solve(M)
main()


q = int(input())
for _q in range(q):
	n = int(input())
	A = [None for i in range(2 * n)]
	for i in range(2 * n):
		A[i] = list(map(int, input().split()))
	res = 0
	for i in range(n):
		for j in range(n):
			res += max(A[i][j], A[2 * n - 1 - i][j], A[i][2 * n - 1 - j], A[2 * n - 1 - i][2 * n - 1 - j])
	print(res)


def maxsum(mat):
	n = len(mat) // 2
	s = 0
	for i in range(n):
		for j in range(n):
			s += max(mat[i][j], mat[2 * n - i - 1][j], mat[i][2 * n - j - 1], mat[2 * n - i - 1][2 * n - j - 1])
	return s
for _ in range(int(input())):
	n = int(input())
	mat = [list(map(int, input().split())) for i in range(2 * n)]
	print(maxsum(mat))


q = int(input())
for ii in range(q):
	n = int(input())
	l = []
	for i in range(2 * n):
		l.append([int(j) for j in input().split()])
	ans = 0
	for i in range(0, n):
		for j in range(0, n):
			ans += max(l[i][j], l[2 * n - i - 1][j], l[i][2 * n - j - 1], l[2 * n - i - 1][2 * n - j - 1])
	print(ans)


q = int(input())
for i in range(q):
	n = int(input())
	arr = []
	for j in range(n * 2):
		temp = [int(x) for x in input().split()]
		arr.append(temp)
	s = 0
	for j in range(n):
		for k in range(n):
			index = 2 * n - 1 - j
			temp = max(arr[j][k], arr[j][-k - 1], arr[index][k], arr[index][-k - 1])
			s += temp
	print(s)


def flipping_the_matrix(n, matrix):
	last = 2 * n - 1
	return sum((max(matrix[i][j], matrix[last - i][j], matrix[i][last - j], matrix[last - i][last - j]) for i in range(n) for j in range(n)))
q = int(input())
for _ in range(q):
	n = int(input())
	matrix = [[int(s) for s in input().split()] for _ in range(2 * n)]
	print(flipping_the_matrix(n, matrix))


q = int(input().strip())
for _1 in range(q):
	n = int(input().strip())
	matrix = []
	for _2 in range(n * 2):
		matrix.append([int(x) for x in input().strip().split(' ')])
	sum = 0
	for i in range(n):
		for j in range(n):
			sum += max([matrix[i][j], matrix[n * 2 - i - 1][j], matrix[i][n * 2 - j - 1], matrix[n * 2 - i - 1][n * 2 - j - 1]])
	print(sum)


q = int(input().strip())
for test in range(q):
	n = int(input().strip())
	m = []
	for r in range(2 * n):
		row = [int(i) for i in input().strip().split()]
		m.append(row)
	s = 0
	for i in range(n):
		for j in range(n):
			n1 = m[i][j]
			n2 = m[2 * n - 1 - i][j]
			n3 = m[i][2 * n - 1 - j]
			n4 = m[2 * n - 1 - i][2 * n - 1 - j]
			s += max([n1, n2, n3, n4])
	print(s)


q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	m = []
	for _ in range(2 * n):
		m.append([int(x) for x in input().strip().split()])
		pass
	x = 0
	for i0 in range(n):
		for j0 in range(n):
			i1 = 2 * n - 1 - i0
			j1 = 2 * n - 1 - j0
			x += max(m[i0][j0], m[i0][j1], m[i1][j0], m[i1][j1])
			pass
		pass
	print(x)
	pass


q = int(input().strip())
for qi in range(q):
	n = int(input().strip())
	n2 = 2 * n
	a = [0] * n2
	sum = 0
	for i in range(n2):
		a[i] = [int(ai) for ai in input().strip().split(' ')]
	for i in range(n):
		for j in range(n):
			j2 = n2 - j - 1
			i2 = n2 - i - 1
			sum += max(a[i][j], a[i][j2], a[i2][j], a[i2][j2])
	print(sum)


def maxSubSum(mat, n):
	tot = 0
	for i in range(n):
		for j in range(n):
			tot += max(mat[i][j], mat[i][2 * n - 1 - j], mat[2 * n - 1 - i][j], mat[2 * n - 1 - i][2 * n - 1 - j])
	print(tot)
for _ in range(int(input().strip())):
	n = int(input().strip())
	mat = []
	for _ in range(2 * n):
		mat.append([int(x) for x in input().strip().split()])
	maxSubSum(mat, n)


t = int(input())
for z in range(t):
	n = int(input())
	tot = []
	l = []
	for _ in range(2 * n):
		l.append([int(x) for x in input().split()])
	for x in range(n):
		for y in range(n):
			tot.append(max(l[x][y], l[x][2 * n - y - 1], l[2 * n - x - 1][y], l[2 * n - x - 1][2 * n - y - 1]))
	print(sum(tot))


def reverse(n, x):
	return list(reversed(range(n)))[x]

def transa(n, i, j):
	return (i, j)

def transb(n, i, j):
	return (reverse(n, i) + n, j)

def transc(n, i, j):
	return (i, reverse(n, j) + n)

def transd(n, i, j):
	return (reverse(n, i) + n, reverse(n, j) + n)
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	matrix = []
	for _ in range(2 * n):
		matrix.append([int(k) for k in input().strip().split()])
	result = 0
	for i in range(n):
		for j in range(n):
			options = [k(n, i, j) for k in [transa, transb, transc, transd]]
			values = [matrix[x][y] for (x, y) in options]
			result = result + max(values)
	print(result)


q = int(input())
for x in range(q):
	n = int(input())
	n2 = n * 2
	a = list()
	maxSum = 0
	for i in range(n2):
		a.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			maxSum += max(a[i][j], a[i][n2 - j - 1], a[n2 - i - 1][j], a[n2 - i - 1][n2 - j - 1])
	print(maxSum)


for q in range(int(input())):
	n = int(input())
	l = []
	for i in range(2 * n):
		l.append([int(x) for x in input().split()])
	t = 0
	for i in range(n):
		for j in range(n):
			t += max(l[i][j], l[i][2 * n - 1 - j], l[2 * n - 1 - i][j], l[2 * n - 1 - i][2 * n - 1 - j])
	print(t)


q = int(input().strip())
mat = []
for i in range(q):
	n = int(input().strip())
	mat = []
	m = 2 * n - 1
	for j in range(2 * n):
		inp = input().strip().split()
		inp = [int(x) for x in inp]
		mat.append(inp)
	ans = 0
	for j in range(n):
		for k in range(n):
			ans += max(mat[j][k], mat[j][m - k], mat[m - j][m - k], mat[m - j][k])
	print(ans)


import sys
sys.setrecursionlimit(30000)
from collections import Counter, defaultdict, deque
from math import ceil, floor, factorial, fsum, isinf, exp, log, log10, log2, isfinite, sqrt
from math import pi as PI, e as E
from math import sin, cos, tan, sinh, cosh, tanh, asin, acos, atan
from fractions import Fraction
from itertools import starmap, tee, chain, filterfalse, combinations as combos
from itertools import permutations as perms, product as prod, combinations_with_replacement as rcombos
from functools import reduce, partial
import operator as ops
from operator import __not__ as notit, __abs__ as absit, __or__ as orit
from bisect import insort_left
from copy import deepcopy
(PHI, PHI2) = ((1 + 5 ** 0.5) / 2, (5 ** 0.5 - 1) / 2)
INF = float('inf')

class TreeNode:

	def __init__(self, v):
		self.val = v
		self.left = None
		self.right = None

def setBit(x, offset):
	return x | 1 << offset

def clearBit(x, offset):
	return x & ~(1 << offset)

def getBit(x, offset):
	return 1 if testBit(x, offset) > 0 else 0

def testBit(x, offset):
	return x & 1 << offset

def flipBitAt(x, offset):
	return x ^ 1 << offset

def flipBits(x, length=-1):
	length = x.bit_length() - 1 if length == -1 else length
	return x ^ (1 << length) - 1

def numBits(x):
	return x.bit_length()

def countOnes(x):
	return bin(x).count('1')

def countZeros(x, length=-1):
	length = x.bit_length() if length == -1 else length
	return length - countOnes(x)

def getList(tcast=str):
	return [tcast(x) for x in input().strip().split(' ')]

def getItems(*tcast):
	return map(lambda f, x: f(x), tcast, getList())

def getVal(tcast=str):
	return tcast(input().strip())

def getMatrix(r, tcast=str):
	return [getList(tcast) for row in range(r)]

def isOdd(n):
	return n & 1 > 0

def isEven(n):
	return not n & 1

def numDigits(n):
	return len(str(n)) - (1 if n < 0 else 0)

def _gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def gcd(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		if cur == 1:
			return cur
		cur = _gcd(cur, n)
	return cur

def _lcm(a, b):
	return a // gcd(a, b) * b

def lcm(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		cur = _lcm(cur, n)
	return cur

def primesUpto(n):
	isp = [True] * (n + 1)
	(isp[0], isp[1]) = (False, False)
	primes = []
	for (i, x) in enumerate(isp):
		if x:
			primes.append(i)
			mults = i * i
			while mults <= n:
				isp[mults] = False
				mults += i
	return primes

def primeFactor(n):
	factors = Counter()
	while not n & 1:
		factors[2] += 1
		n >>= 1
	trynum = 3
	while trynum <= ceil(sqrt(n)):
		while n % trynum == 0:
			factors[trynum] += 1
			n //= trynum
		trynum += 2
	if n != 1:
		factors[n] += 1
	return factors

def isPrime(n):
	if n & 1 and n >= 2:
		trynum = 3
		limit = ceil(sqrt(n))
		while trynum < limit:
			if n % trynum == 0:
				return False
			trynum += 2
		else:
			return True
	else:
		return False

def nthFib(n):
	if n <= 2:
		return 1
	else:
		(a, b) = (1, 1)
		while n > 2:
			(a, b) = (b, a + b)
			n -= 1
		return b

def zipNWith(f, *x):
	return (f(y) for y in zip(*x))

def zipWith(f, xs, ys):
	return (f(x, y) for (x, y) in zip(xs, ys))

def flatten(xs):
	return reduce(ops.concat, xs)

def quantify(pred, it):
	return sum(map(pred, it))

def dotproduct(xs, ys):
	return sum(map(ops.mul, xs, ys))

def adjpairs(it):
	(a, b) = tee(it)
	next(b, None)
	return zip(a, b)

def bipartition(pred, it):
	(t, f) = tee(it)
	return (filter(pred, t), filterfalse(pred, f))

def powerset(it):
	s = list(it)
	return chain.from_iterable((combos(s, r) for r in range(len(s) + 1)))

def depProduct(bounds, f=lambda y: y + 1, g=lambda *x: tuple(x)):
	args = [-1]
	nbounds = len(bounds)
	while args:
		n = len(args)
		args[-1] += 1
		if args[-1] >= bounds[n - 1]:
			args.pop()
		elif n == nbounds:
			yield g(*args)
		else:
			_f = f[n] if type(f) == list else f
			args.append(_f(args[-1]) - 1)

def revEnumerate(xs):
	n = len(xs) - 1
	for (i, x) in enumerate(reversed(xs)):
		yield (n - i, x)
ncases = getVal(int)
for k in range(ncases):
	n = getVal(int)
	nn = n * 2
	mat = getMatrix(nn, int)
	total = 0
	for i in range(n):
		for j in range(n):
			total += max(mat[i][j], mat[nn - i - 1][j], mat[i][nn - j - 1], mat[nn - i - 1][nn - j - 1])
	print(total)


def maximize(M):
	total = 0
	m = len(M)
	n = m // 2
	for i in range(n):
		for j in range(n):
			total += max(M[i][j], M[m - i - 1][j], M[i][m - j - 1], M[m - i - 1][m - j - 1])
	return total

def main():
	q = int(input())
	result = [None] * q
	for i in range(q):
		n = int(input())
		matrix = [None] * (2 * n)
		for j in range(2 * n):
			matrix[j] = [int(x) for x in input().split()]
		result[i] = maximize(matrix)
	for i in range(q):
		print(result[i])
main()


q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	arr = []
	for _ in range(2 * n):
		arr.append([int(x) for x in input().strip().split(' ')])
	max_sum = 0
	for r in range(n):
		for c in range(n):
			max_sum += max(arr[r][c], arr[2 * n - 1 - r][c], arr[r][2 * n - 1 - c], arr[2 * n - 1 - r][2 * n - 1 - c])
	print(max_sum)


for _ in range(int(input())):
	matrix = [list(map(int, input().split())) for __ in range(2 * int(input()))]
	result = 0
	for i in range(len(matrix) // 2):
		for j in range(len(matrix[i]) // 2):
			result += max(matrix[i][j], matrix[-1 - i][j], matrix[i][-1 - j], matrix[-1 - i][-1 - j])
	print(result)


q = int(input())
for p in range(0, q):
	n = int(input())
	matrix = [None] * 2 * n
	for i in range(0, 2 * n):
		matrix[i] = [int(x) for x in input().split()]
	s = 0
	for i in range(0, n):
		for j in range(0, n):
			s += max(matrix[i][j], matrix[2 * n - 1 - i][j], matrix[i][2 * n - 1 - j], matrix[2 * n - 1 - i][2 * n - 1 - j])
	print(s)


def solve(matrix, n):
	res = 0
	size = 2 * n
	for i in range(n):
		for j in range(n):
			res += max(matrix[i][j], matrix[i][size - j - 1], matrix[size - i - 1][j], matrix[size - i - 1][size - j - 1])
	return res
q = int(input())
for i in range(q):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append(list(map(int, input().split())))
	print(solve(matrix, n))


from time import sleep

def print_matrix(matrix):
	for row in range(len(matrix)):
		print(''.join(('{:>4}'.format(e) for e in matrix[row])))
	print()

def improve(matrix, n):

	def reverse_row(row):
		matrix[row] = list(reversed(matrix[row]))

	def reverse_column(col):
		for row in range(n):
			other_row = len(matrix) - row - 1
			(matrix[row][col], matrix[other_row][col]) = (matrix[other_row][col], matrix[row][col])

	def is_row_perfect(row):
		return sum(matrix[row][:n]) >= sum(matrix[row][n:])

	def is_column_perfect(col):
		return sum((matrix[row][col] for row in range(n))) >= sum((matrix[row][col] for row in range(n, len(matrix))))
	for row in range(len(matrix)):
		if not is_row_perfect(row):
			reverse_row(row)
			return True
	for col in range(len(matrix)):
		if not is_column_perfect(col):
			reverse_column(col)
			return True
	return False

def main():
	for _ in range(int(input())):
		n = int(input())
		size = 2 * n
		matrix = [None] * size
		for row in range(size):
			matrix[row] = list(map(int, input().split()))
		total = 0
		for row in range(n):
			for column in range(n):
				other_row = size - 1 - row
				other_column = size - 1 - column
				locations = [(row, column), (other_row, column), (row, other_column), (other_row, other_column)]
				total += max((matrix[r][c] for (r, c) in locations))
		print(total)
main()


q = int(input())
for _ in range(q):
	n = int(input())
	matrix = [list(map(int, input().split())) for _ in range(2 * n)]
	max_sum = 0
	for i in range(n):
		for j in range(n):
			i_sym = 2 * n - i - 1
			j_sym = 2 * n - j - 1
			max_sum += max(matrix[i][j], matrix[i][j_sym], matrix[i_sym][j], matrix[i_sym][j_sym])
	print(max_sum)


q = int(input())
for query in range(q):
	n = int(input())
	N = 2 * n
	matrix_current = [[0] * N] * N
	for r in range(N):
		each_row = list(map(int, input().split()))
		matrix_current[r] = each_row
	best_sum = 0
	for rr in range(n):
		for cc in range(n):
			current_val = matrix_current[rr][cc]
			candidate_1 = matrix_current[rr][N - cc - 1]
			candidate_2 = matrix_current[N - rr - 1][cc]
			candidate_3 = matrix_current[N - rr - 1][N - cc - 1]
			best_sum += max(current_val, candidate_1, candidate_2, candidate_3)
	print(best_sum)


q = eval(input())
for i in range(q):
	n = eval(input())
	matrix = []
	for j in range(2 * n):
		matrix.append([int(x) for x in input().split()])
	sum = 0
	for j in range(n):
		for k in range(n):
			sum += max(matrix[j][k], matrix[j][-k - 1], matrix[-j - 1][k], matrix[-j - 1][-k - 1])
	print(sum)


def rotate(arr):
	n = len(arr)
	m = n // 2
	ret = 0
	for i in range(m):
		for j in range(m):
			ret += max([arr[i][j], arr[n - 1 - i][j], arr[i][n - 1 - j], arr[n - 1 - i][n - 1 - j]])
	return ret
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	arr = [list(map(int, input().strip().split())) for _ in range(2 * n)]
	ans = rotate(arr)
	print(ans)


q = int(input().strip())
for __ in range(q):
	n = int(input().strip())
	x = 2 * n - 1
	ans = 0
	g = []
	for n0 in range(2 * n):
		g.append([int(i) for i in input().strip().split()])
	for i in range(n):
		for j in range(n):
			ans += max(g[i][j], g[x - i][j], g[i][x - j], g[x - i][x - j])
	print(ans)


q = int(input())
answer = list()
for _ in range(q):
	n = int(input())
	arr = list()
	for i in range(n * 2):
		arr.append(list(map(int, input().split())))
	result = 0
	for i in range(n):
		for j in range(n):
			result += max([arr[i][j], arr[i][n * 2 - j - 1], arr[n * 2 - i - 1][j], arr[n * 2 - i - 1][n * 2 - j - 1]])
	answer.append(result)
print('\n'.join(map(str, answer)))


test = int(input())
for g in range(test):
	n = int(input())
	m = 2 * n
	matrix = [[0 for x in range(m)] for y in range(m)]
	for i in range(2 * n):
		s = input().split()
		for j in range(2 * n):
			matrix[i][j] = int(s[j])
	new = [[0 for x in range(n)] for y in range(n)]
	for i in range(n):
		for j in range(n):
			new[i][j] = max(matrix[i][j], matrix[i][m - j - 1], matrix[m - i - 1][j], matrix[m - i - 1][m - j - 1])
	c = 0
	for i in range(n):
		for j in range(n):
			c += new[i][j]
	print(c)


query = int(input())
for i in range(0, query):
	n = int(input())
	matrix = []
	for j in range(0, 2 * n):
		matrix = matrix + [[int(a) for a in input().strip().split(' ')]]
	ans = 0
	for k in range(0, n):
		for l in range(0, n):
			value = matrix[k][l]
			if value < matrix[2 * n - k - 1][l]:
				value = matrix[2 * n - k - 1][l]
			if value < matrix[k][2 * n - l - 1]:
				value = matrix[k][2 * n - l - 1]
			if value < matrix[2 * n - k - 1][2 * n - l - 1]:
				value = matrix[2 * n - k - 1][2 * n - l - 1]
			ans = ans + value
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = [0] * 2 * n
	for j in range(2 * n):
		a[j] = [int(x) for x in input().split()]
	res = 0
	for y in range(n):
		for z in range(n):
			res = res + max(int(a[y][z]), int(a[y][2 * n - 1 - z]), int(a[2 * n - 1 - y][z]), int(a[2 * n - 1 - y][2 * n - 1 - z]))
	print(res)


nt = int(input().strip())
for t in range(nt):
	n = int(input().strip())
	m = []
	for r in range(2 * n):
		m.append([int(c) for c in input().strip().split()])
	sum = 0
	for r in range(n):
		for c in range(n):
			sum += max(m[r][c], m[r][2 * n - 1 - c], m[2 * n - 1 - r][c], m[2 * n - 1 - r][2 * n - 1 - c])
	print(sum)


queries = int(input())
for q in range(queries):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append([int(elem) for elem in input().split()])
	max_sum = 0
	for row in range(n):
		for col in range(n):
			a = matrix[row][col]
			b = matrix[-row - 1][col]
			c = matrix[row][-col - 1]
			d = matrix[-row - 1][-col - 1]
			max_sum += max(a, b, c, d)
	print(max_sum)


def find_max_q_sum(arr, n):
	tot = 0
	for i in range(n):
		for j in range(n):
			tot += max(arr[i][j], arr[2 * n - i - 1][j], arr[2 * n - i - 1][2 * n - j - 1], arr[i][2 * n - j - 1])
	return tot
q = int(input())
for i in range(q):
	n = int(input())
	arr = [[] for k in range(2 * n)]
	for k in range(2 * n):
		arr[k] = list(map(int, input().split()))
	print(find_max_q_sum(arr, n))


read_line = lambda : (int(i) for i in input().split())

def work():
	n = int(input())
	ans = [[0 for j in range(n)] for i in range(n)]
	for i_ in range(2 * n):
		i = min(i_, 2 * n - 1 - i_)
		for (j_, x) in enumerate(read_line()):
			j = min(j_, 2 * n - 1 - j_)
			ans[i][j] = max(ans[i][j], x)
	return sum((sum(_) for _ in ans))
for t in range(int(input())):
	print(work())


num = int(input())
for i in range(num):
	n = int(input())
	m = []
	for i in range(2 * n):
		m.append([int(i) for i in input().split()])
	s = []
	for i in range(n):
		for j in range(n):
			s.append(max([m[i][j], m[i][2 * n - j - 1], m[2 * n - i - 1][j], m[2 * n - i - 1][2 * n - j - 1]]))
	print(sum(s))


for q in range(int(input())):
	n = int(input())
	mat = []
	for i in range(2 * n):
		mat.append([int(x) for x in input().split()])
	F = 0
	for i in range(n):
		for j in range(n):
			t = 0
			if mat[j][i] > t:
				t = mat[j][i]
			if mat[2 * n - 1 - j][i] > t:
				t = mat[2 * n - 1 - j][i]
			if mat[j][2 * n - 1 - i] > t:
				t = mat[j][2 * n - 1 - i]
			if mat[2 * n - 1 - j][2 * n - 1 - i] > t:
				t = mat[2 * n - 1 - j][2 * n - 1 - i]
			F += t
	print(F)


q = int(input())
for _ in range(q):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append([int(x) for x in input().split()])
	answer = 0
	for i in range(n):
		for j in range(n):
			answer += max(matrix[i][j], matrix[2 * n - 1 - i][j], matrix[i][2 * n - 1 - j], matrix[2 * n - 1 - i][2 * n - 1 - j])
	print(answer)


q = int(input())
for i in range(q):
	n = int(input())
	v = []
	for j in range(2 * n):
		v.append([int(i) for i in input().split()])
	s = 0
	for j in range(n):
		for k in range(n):
			s = s + max(v[j][k], v[j][2 * n - k - 1], v[2 * n - j - 1][k], v[2 * n - j - 1][2 * n - k - 1])
	print(s)


for _ in range(int(input())):
	n = int(input())
	temp = []
	sums = 0
	for _ in range(2 * n):
		temp.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			sums += max(temp[i][j], temp[2 * n - 1 - i][j], temp[2 * n - 1 - i][2 * n - 1 - j], temp[i][2 * n - 1 - j])
	print(sums)


q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	a = [[int(i) for i in input().strip().split(' ')] for _ in range(2 * n)]
	total = 0
	for i in range(n):
		for j in range(n):
			total += max(a[i][j], a[i][2 * n - j - 1], a[2 * n - i - 1][j], a[2 * n - i - 1][2 * n - j - 1])
	print(total)


def maxx(a, i, j):
	n = len(a) - 1
	return max(a[i][j], a[i][n - j], a[n - i][j], a[n - i][n - j])
t = int(input())
for xx in range(t):
	n = 2 * int(input())
	a = []
	b = []
	for i in range(n):
		b = input().split()
		b = [int(x) for x in b]
		a.append(b)
		b = []
	summ = 0
	for i in range(n // 2):
		for j in range(n // 2):
			summ = summ + maxx(a, i, j)
	print(summ)


def max1(a, i, j):
	n = len(a) - 1
	return max(a[i][j], a[i][n - j], a[n - i][j], a[n - i][n - j])
t = int(input())
for xxx in range(t):
	n = 2 * int(input())
	p = []
	b = []
	for i in range(n):
		b = input().split()
		b = [int(x) for x in b]
		p.append(b)
		b = []
	sum = 0
	for i in range(n // 2):
		for j in range(n // 2):
			sum = sum + max1(p, i, j)
	print(sum)


def maxof(a, i, j):
	n = len(a) - 1
	return max(a[i][j], a[i][n - j], a[n - i][j], a[n - i][n - j])
t = int(input())
for t in range(t):
	n = 2 * int(input())
	a = []
	b = []
	for i in range(n):
		b = input().split()
		b = [int(x) for x in b]
		a.append(b)
		b = []
	sums = 0
	for i in range(n // 2):
		for j in range(n // 2):
			sums = sums + maxof(a, i, j)
	print(sums)


queries = int(input())
for q in range(queries):
	n = int(input())
	width = 2 * n
	arr = []
	for i in range(width):
		row = [int(i) for i in input().strip().split()]
		arr.append(row)
	total = 0
	for i in range(n):
		for j in range(n):
			number = arr[i][j]
			if number < arr[i][width - 1 - j]:
				number = arr[i][width - 1 - j]
			if number < arr[width - 1 - i][j]:
				number = arr[width - 1 - i][j]
			if number < arr[width - 1 - i][width - 1 - j]:
				number = arr[width - 1 - i][width - 1 - j]
			total += number
	print(total)


import sys

def max_matrix(mx, n):
	total = 0
	for k in range(n):
		for off in range(n):
			total += max(mx[k][off], mx[k][-(1 + off)], mx[-(k + 1)][off], mx[-(k + 1)][-(1 + off)])
	return total
lines = sys.stdin.readlines()
q = int(lines.pop(0).strip())
for i in range(q):
	n = int(lines.pop(0).strip())
	mx = []
	for j in range(2 * n):
		mx.append([int(x) for x in lines.pop(0).strip().split(' ')])
	print(max_matrix(mx, n))


tests = int(input())
for _ in range(tests):
	n = int(input())
	grid = []
	for i in range(n * 2):
		lst = list(map(int, input().split()))
		grid.append(lst)
	ans = 0
	m = 2 * n
	for i in range(n):
		for j in range(n):
			ans += max(grid[i][j], max(grid[m - i - 1][m - j - 1], max(grid[m - i - 1][j], grid[i][m - j - 1])))
	print(ans)


q = int(input())
for _ in range(q):
	n = int(input())
	total = 0
	queue = []
	for _ in range(n):
		queue.append(list(map(int, input().split())))
	for _ in range(n):
		rowt = queue.pop()
		rowb = list(map(int, input().split()))
		total += sum(map(max, zip(rowt[:n], rowt[n:][::-1], rowb[:n], rowb[n:][::-1])))
	print(total)


num_queries = int(input())
for _ in range(num_queries):
	n = int(input())
	matrix = []
	for _ in range(2 * n):
		row = [int(i) for i in input().split()]
		matrix.append(row)
	quadrant = []
	for r in range(n):
		for c in range(n):
			quadrant.append((r, c))
	qmax = 0
	for (r, c) in quadrant:
		row_choices = (r, 2 * n - r - 1, r, 2 * n - r - 1)
		col_choices = (c, c, 2 * n - c - 1, 2 * n - c - 1)
		cell_choices = [matrix[r][c] for (r, c) in zip(row_choices, col_choices)]
		qmax += max(cell_choices)
	print(qmax)


import sys
q = int(input())
for a in range(q):
	n = int(input())
	m = []
	for b in range(2 * n):
		g = [int(x) for x in input().split()]
		m.append(g)
	ss = 0
	for i in range(n):
		for j in range(n):
			s = []
			s.append(m[i][j])
			s.append(m[i][2 * n - 1 - j])
			s.append(m[2 * n - 1 - i][j])
			s.append(m[2 * n - 1 - i][2 * n - 1 - j])
			ss += max(s)
	print(ss)


t = int(input())
for _ in range(t):
	n = int(input())
	matrix = []
	for _ in range(2 * n):
		matrix.append([int(k) for k in input().strip().split()])
	total = 0
	for i in range(n):
		for j in range(n):
			total += max(matrix[i][j], matrix[2 * n - 1 - i][j], matrix[i][2 * n - 1 - j], matrix[2 * n - 1 - i][2 * n - 1 - j])
	print(total)


for _ in range(int(input())):
	n = int(input())
	g = [list(map(int, input().split())) for _ in range(2 * n)]
	r = 0
	for i in range(n):
		tmp = list()
		for j in range(n):
			tmp.append(max(g[i][j], g[2 * n - i - 1][j], g[i][2 * n - j - 1], g[2 * n - i - 1][2 * n - j - 1]))
		r += sum(tmp)
	print(r)


for _ in range(int(input())):
	n = int(input())
	l = [list(map(int, input().split())) for _ in range(2 * n)]
	s = 0
	for i in range(n):
		for j in range(n):
			s += max(l[i][j], l[2 * n - 1 - i][j], l[i][2 * n - 1 - j], l[2 * n - 1 - i][2 * n - 1 - j])
	print(s)


from sys import stdin

def getfromline(s):
	s = s.rstrip()
	s = s.split(' ')
	s = [int(i) for i in s]
	return s

def getdata():
	mxs = []
	s = stdin.readline()
	(q,) = getfromline(s)
	for i in range(q):
		s = stdin.readline()
		(sz,) = getfromline(s)
		mxs.append([])
		for j in range(sz * 2):
			s = stdin.readline()
			buf = getfromline(s)
			mxs[i].append(buf)
	return mxs

def getmaxmx(mxs):
	for i in mxs:
		rng = len(i[0])
		for j in range(rng // 2):
			for k in range(rng // 2):
				i[j][k] = max(i[j][k], i[j][rng - 1 - k], i[rng - 1 - j][k], i[rng - 1 - j][rng - 1 - k])

def putresult(mxs):
	res = []
	sum = 0
	for i in mxs:
		for j in range(len(i) // 2):
			for k in range(len(i) // 2):
				sum += i[j][k]
		res.append(sum)
		sum = 0
	return res

def run():
	res = 0
	mxs = getdata()
	getmaxmx(mxs)
	for i in putresult(mxs):
		print(i)
run()


def solve(matrix):
	N = len(matrix[0])
	n = len(matrix[0]) // 2
	result = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			possibilities = [(i, j), (N - 1 - i, j), (i, N - 1 - j), (N - 1 - i, N - 1 - j)]
			for item in possibilities:
				tmp = matrix[item[0]][item[1]]
				if tmp > result[i][j]:
					result[i][j] = tmp
	return sum([sum(row) for row in result])
q = int(input())
for _ in range(q):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append(list(map(int, input().split())))
	print(solve(matrix))


q = int(input())
for t in range(q):
	n = int(input())
	grid = [[int(j) for j in input().split()] for i in range(2 * n)]
	ans = 0
	for i in range(n):
		for j in range(n):
			ans += max(grid[i][j], grid[i][2 * n - j - 1], grid[2 * n - i - 1][j], grid[2 * n - i - 1][2 * n - j - 1])
	print(ans)


for caso in range(int(input())):
	n = int(input())
	matriz = []
	maximo = 0
	for i in range(2 * n):
		fila = [int(x) for x in input().strip().split(' ')]
		matriz.append(fila)
	for i in range(n):
		for j in range(n):
			maximo += max(matriz[i][j], matriz[i][2 * n - j - 1], matriz[2 * n - i - 1][j], matriz[2 * n - i - 1][2 * n - j - 1])
	print(maximo)


q = int(input())
while q > 0:
	n = int(input())
	mat = [[int(i) for i in input().strip().split()] for j in range(2 * n)]
	sum = 0
	for i in range(n):
		for j in range(n):
			sum += max(mat[i][j], mat[i][2 * n - 1 - j], mat[2 * n - 1 - i][j], mat[2 * n - 1 - i][2 * n - 1 - j])
	print(sum)
	q -= 1


import sys
q = int(input().strip())
for z in range(q):
	n = int(input().strip())
	m = [[0 for x in range(2 * n)] for y in range(2 * n)]
	r = 0
	for i in range(2 * n):
		m[i] = [int(x) for x in input().strip().split()]
	for i in range(int(n)):
		for j in range(int(n)):
			v = max(m[i][j], m[i][2 * n - 1 - j], m[2 * n - 1 - i][j], m[2 * n - 1 - i][2 * n - 1 - j])
			r += v
	print(r)


import math
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	a = [[0 for j in range(2 * n)] for i in range(2 * n)]
	for x in range(2 * n):
		c = [int(c_temp) for c_temp in input().strip().split(' ')]
		a[x] = c
	v = 0
	for i in range(n):
		for j in range(n):
			l = []
			l.append(a[i][j])
			l.append(a[2 * n - 1 - i][j])
			l.append(a[i][2 * n - 1 - j])
			l.append(a[2 * n - 1 - i][2 * n - 1 - j])
			maxv = max(l)
			v += maxv
	print(v)


def simple_solve(N, data):
	total = 0
	for i in range(N):
		for j in range(N):
			total += max(data[i][j], data[2 * N - i - 1][j], data[2 * N - i - 1][2 * N - j - 1], data[i][2 * N - j - 1])
	return total
T = int(input())
for t in range(T):
	N = int(input())
	data = []
	for n in range(N * 2):
		data.append(list((int(i) for i in input().split())))
	print(simple_solve(N, data))


def matrix():
	n = int(input())
	rows = []
	for i in range(2 * n):
		rows.append([int(temp) for temp in input().strip().split()])
	max_sum = 0
	for i in range(n):
		for j in range(n):
			r = max([rows[i][j], rows[i][-(j + 1)], rows[-(i + 1)][j], rows[-(i + 1)][-(j + 1)]])
			max_sum += r
	return max_sum
q = int(input())
for i in range(q):
	print(matrix())


q = int(input())
for _ in range(q):
	n = int(input())
	nums = []
	for _ in range(n * 2):
		nums.append([int(n) for n in input().split()])
	maxSum = 0
	for r in range(n):
		for c in range(n):
			maxSum += max(nums[r][c], nums[2 * n - 1 - r][c], nums[r][2 * n - 1 - c], nums[2 * n - 1 - r][2 * n - 1 - c])
	print(maxSum)


q = int(input())
for _ in range(q):
	n = int(input())
	matrix = []
	total = 0
	for _ in range(2 * n):
		lst = list(map(int, input().split()))
		matrix.append(lst)
	for i in range(n):
		for j in range(n):
			top_left = matrix[i][j]
			top_right = matrix[i][-(j + 1)]
			bottom_left = matrix[-(i + 1)][j]
			bottom_right = matrix[-(i + 1)][-(j + 1)]
			total += max(top_left, top_right, bottom_left, bottom_right)
	print(total)


query_count = int(input().strip())
for q in range(query_count):
	n = int(input().strip())
	arr = []
	for i in range(2 * n):
		arr.append([int(x) for x in input().strip().split(' ')])
	total = 0
	for i in range(n):
		for j in range(n):
			total += max(arr[i][j], arr[i][2 * n - j - 1], arr[2 * n - i - 1][j], arr[2 * n - i - 1][2 * n - j - 1])
	print(total)


import sys

def main():
	q = int(input())
	for i in range(q):
		n = int(input())
		matrix = []
		for j in range(2 * n):
			row = list(map(int, input().split()))
			matrix.append(row)
		total = 0
		for a in range(n):
			for b in range(n):
				nums = []
				nums.append(matrix[a][b])
				nums.append(matrix[a][2 * n - 1 - b])
				nums.append(matrix[2 * n - 1 - a][b])
				nums.append(matrix[2 * n - 1 - a][2 * n - 1 - b])
				total = total + max(nums)
		print(total)
main()


for _ in range(int(input())):
	a = []
	n = int(input())
	m = 2 * n
	for i in range(m):
		a.append(list(map(int, input().split())))
	sum = 0
	for i in range(n):
		for j in range(n):
			c = max(a[i][j], a[i][m - j - 1], a[m - i - 1][j], a[m - i - 1][m - j - 1])
			sum += c
	print(sum)


q = int(input())
for _o in range(q):
	n = int(input())
	mat = []
	for _ in range(2 * n):
		mat.append(list(map(int, input().split())))
	s = 0
	for i in range(n):
		for j in range(n):
			s += max(mat[i][j], mat[i][2 * n - 1 - j], mat[2 * n - 1 - i][j], mat[2 * n - 1 - i][2 * n - 1 - j])
	print(s)


q = int(input())
cnt = 0
while cnt < q:
	sum = 0
	n = int(input())
	m = [[int(i) for i in input().strip().split(' ')] for x in range(2 * n)]
	x = 0
	while x < n:
		y = 0
		while y < n:
			sum += max(m[x][y], m[x][2 * n - y - 1], m[2 * n - x - 1][y], m[2 * n - x - 1][2 * n - y - 1])
			y += 1
		x += 1
	print(sum)
	cnt += 1


q = int(input())
for _ in range(q):
	n = int(input())
	m = []
	res = 0
	for _ in range(2 * n):
		m.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			res += max(m[n + i][n + j], m[n - 1 - i][n - 1 - j], m[n + i][n - 1 - j], m[n - 1 - i][n + j])
	print(res)


Q = int(input())
for q in range(Q):
	N = int(input())
	(matrix, total) = ([], 0)
	for n in range(2 * N):
		matrix.append(list(map(int, input().split())))
	for i in range(N):
		for j in range(N):
			total += max(matrix[i][j], matrix[2 * N - i - 1][j], matrix[i][2 * N - j - 1], matrix[2 * N - i - 1][2 * N - j - 1])
	print(total)


t = int(input().strip())
for test in range(t):
	n = int(input().strip())
	martix = []
	for i in range(n * 2):
		row = [int(a_temp) for a_temp in input().strip().split(' ')]
		martix.append(row)
	sum = 0
	for i in range(n):
		for j in range(n):
			sum += max(martix[i][j], martix[i][n * 2 - 1 - j], martix[n * 2 - 1 - i][j], martix[n * 2 - 1 - i][n * 2 - 1 - j])
	print(sum)


Q = int(input())
result = []
for q in range(Q):
	N = int(input())
	matrix = []
	for t in range(2 * N):
		matrix.append([int(t) for t in input().strip().split()])
	m_sum = 0
	for i in range(N):
		for j in range(N):
			m_sum += max(matrix[i][j], matrix[2 * N - i - 1][j], matrix[i][2 * N - j - 1], matrix[2 * N - i - 1][2 * N - j - 1])
	result.append(str(m_sum))
print('\n'.join(result))


import sys
q = int(input())
for kk in range(q):
	n = int(input())
	e = []
	for y in range(2 * n):
		e.append([int(i) for i in input().split()])
	s = 0
	j = 2 * n - 1
	for x in range(n):
		for y in range(n):
			s += max(e[x][y], e[x][j - y], e[j - x][y], e[j - x][j - y])
	print(s)


N = int(input())
for test in range(N):
	n = int(input())
	matrix = []
	for i in range(2 * n):
		matrix.append([int(i) for i in input().split()])
	bestsum = 0
	for row in range(n):
		for col in range(n):
			bestsum += max(matrix[row][col], matrix[row][2 * n - col - 1], matrix[2 * n - row - 1][col], matrix[2 * n - row - 1][2 * n - col - 1])
	print(bestsum)


queries = int(input().strip())
for q in range(queries):
	max_sum = 0
	matrix = []
	top_left_submatrix = []
	top_right_submatrix = []
	bottom_left_submatrix = []
	bottom_right_submatrix = []
	n = int(input().strip())
	for row in range(2 * n):
		matrix.append(list(map(int, input().strip().split())))
	for row in range(n):
		top_left_submatrix.append(matrix[row][:n])
		top_right_submatrix.append(matrix[row][n:])
	for row in range(n, 2 * n):
		bottom_left_submatrix.append(matrix[row][:n])
		bottom_right_submatrix.append(matrix[row][n:])
	for i in range(0, n):
		top_right_submatrix[i] = list(reversed(top_right_submatrix[i]))
	bottom_left_submatrix = list(reversed(bottom_left_submatrix))
	bottom_right_submatrix = list(reversed(bottom_right_submatrix))
	for i in range(0, n):
		bottom_right_submatrix[i] = list(reversed(bottom_right_submatrix[i]))
	for r in range(0, n):
		for c in range(0, n):
			max_sum += max(top_left_submatrix[r][c], top_right_submatrix[r][c], bottom_left_submatrix[r][c], bottom_right_submatrix[r][c])
	print(max_sum)


q = int(input())
for _ in range(q):
	n = int(input())
	m = []
	for _ in range(2 * n):
		m.append([int(i) for i in input().split()])
	ans = 0
	for i in range(n):
		for j in range(n):
			if i >= n:
				if j >= n:
					ans += max(m[i][j], m[n - (i - n + 1)][j], m[i][n - (j - n + 1)], m[n - (i - n + 1)][n - (j - n + 1)])
				else:
					ans += max(m[i][j], m[n - (i - n + 1)][j], m[i][n + (n - 1 - j)], m[n - (i - n + 1)][n + (n - j - 1)])
			elif j >= n:
				ans += max(m[i][j], m[n + (n - i - 1)][j], m[i][n - (j - n + 1)], m[n + (n - i - 1)][n - (j - n + 1)])
			else:
				ans += max(m[i][j], m[n + (n - i - 1)][j], m[i][n + (n - j - 1)], m[n + (n - i - 1)][n + (n - j - 1)])
	print(ans)


q = int(input())
for caseIdx in range(1, q + 1):
	n = int(input())
	mat = []
	for r in range(2 * n):
		row = list(map(int, input().strip().split(' ')))
		mat.append(row)
	maxSum = 0
	maxIdx = 2 * n - 1
	for i in range(n):
		for j in range(n):
			maxSum += max([mat[i][j], mat[maxIdx - i][j], mat[i][maxIdx - j], mat[maxIdx - i][maxIdx - j]])
	print(maxSum)


t = int(input())
while t:
	myList = []
	list1 = []
	n = int(input())
	for i in range(0, 2 * n):
		myList.append(list((int(i) for i in input().split())))
	temp = []
	s = 0
	for i in range(n):
		for j in range(n):
			temp.append(myList[i][j])
			temp.append(myList[i][2 * n - 1 - j])
			temp.append(myList[2 * n - 1 - i][j])
			temp.append(myList[2 * n - 1 - i][2 * n - 1 - j])
			s += max(temp)
			temp[:] = []
	print(s)
	t = t - 1