Chef is learning linear algebra. Recently, he learnt that for a square matrix $M$, $\mathop{\rm trace}(M)$ is defined as the sum of all elements on the main diagonal of $M$ (an element lies on the main diagonal if its row index and column index are equal).
Now, Chef wants to solve some excercises related to this new quantity, so he wrote down a square matrix $A$ with size $N\times N$. A square submatrix of $A$ with size $l\times l$ is a contiguous block of $l\times l$ elements of $A$. Formally, if $B$ is a submatrix of $A$ with size $l\times l$, then there must be integers $r$ and $c$ ($1\le r, c \le N+1-l$) such that $B_{i,j} = A_{r+i-1, c+j-1}$ for each $1 \le i, j \le l$.
Help Chef find the maximum trace of a square submatrix of $A$.

-----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$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $N$ space-separated integers $A_{i,1}, A_{i,2}, \dots, A_{i, N}$ denoting the $i$-th row of the matrix $A$.

-----Output-----
For each test case, print a single line containing one integer — the maximum possible trace.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 100$
- $1 \le A_{i,j} \le 100$ for each valid $i, j$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
1
3
1 2 5
6 3 4
2 7 1

-----Example Output-----
13

-----Explanation-----
Example case 1: The submatrix with the largest trace is 
6 3
2 7

which has trace equal to $6 + 7 = 13$. (This submatrix is obtained for $r=2, c=1, l=2$.)

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	N = int(input())
	lst = [list(map(int, input().split())) for m in range(N)]
	maxTrace = 0
	for j in range(N):
		diagSum = 0
		for i in range(N - j):
			diagSum += lst[i][i + j]
		if diagSum > maxTrace:
			maxTrace = diagSum
	for i in range(N):
		diagSum = 0
		for j in range(N - i):
			diagSum += lst[i + j][j]
		if diagSum > maxTrace:
			maxTrace = diagSum
	print(maxTrace)


T = int(input())
for k in range(T):
	N = int(input())
	c = []
	for i in range(N):
		a = [int(item) for item in input().split(' ')]
		c.append(a)
	sub = []
	for i in range(N):
		s = 0
		for j in range(N - i):
			s += c[j][i + j]
		sub.append(s)
	for i in range(1, N):
		s = 0
		for j in range(N - i):
			s += c[i + j][j]
		sub.append(s)
	print(max(sub))


for i in range(int(input())):
	traces = []
	n = int(input())
	matrix = [list(map(int, input().split())) for _ in range(n)]
	for i in range(n):
		m = [l[n - (i + 1):] for l in matrix[:i + 1]]
		trace = 0
		for j in range(i + 1):
			trace += m[j][j]
		traces.append(trace)
	for i in range(n):
		m = [l[:i + 1] for l in matrix[n - (i + 1):]]
		trace = 0
		for j in range(i + 1):
			trace += m[j][j]
		traces.append(trace)
	print(max(traces))


for _ in range(int(input())):
	n = int(input())
	matrix = []
	for i in range(0, n):
		arr = list(map(int, input().strip().split()))
		matrix.append(arr)
	allt = []
	for i in range(0, n):
		(x, y) = (0, 0 + i)
		temp = 0
		while x < n and y < n:
			temp += matrix[x][y]
			x += 1
			y += 1
		allt.append(temp)
	for i in range(0, n):
		(x, y) = (0 + i, 0)
		temp = 0
		while x < n and y < n:
			temp += matrix[x][y]
			x += 1
			y += 1
		allt.append(temp)
	print(max(list(set(allt))))


a = int(input())
for i in range(0, a):
	h = int(input())
	f = []
	su = []
	for j in range(0, h):
		f.append(list(map(int, input().split())))
	for k in range(0, h):
		s = 0
		s1 = 0
		for l in range(0, k + 1):
			s = s + f[l][h + l - k - 1]
			s1 = s1 + f[h + l - k - 1][l]
		su.append(s)
		su.append(s1)
	print(max(su))


for _ in range(int(input())):
	a = int(input())
	s = [list(map(int, input().split())) for m in range(a)]
	max_trace = 0
	for i in range(a):
		s1 = 0
		for j in range(a - i):
			s1 += s[j][j + i]
		if s1 > max_trace:
			max_trace = s1
	for i in range(a):
		s1 = 0
		for j in range(a - i):
			s1 += s[j + i][j]
		if s1 > max_trace:
			max_trace = s1
	print(max_trace)


t = int(input())
for i in range(t):
	l = int(input())
	a = []
	for i in range(l):
		a.append(list(map(int, input().split())))
		res = 0
	for i in range(l):
		res += a[i][i]
	maxi = 0
	k = 0
	for i in range(0, l - 1):
		p = 0
		r = 0
		k += 1
		for j in range(0, l - 1):
			if j + k < l:
				p += a[j][j + k]
				r += a[j + k][j]
		maxi = max(p, r, maxi)
	maxi = max(maxi, res)
	print(maxi)


import sys

def trace(a, n):
	maxx = 0
	for i in range(n):
		for j in range(n):
			summ = 0
			index = 0
			while j + index < n and i + index < n:
				summ += a[i + index][j + index]
				index += 1
			if summ > maxx:
				maxx = summ
	return maxx
t = int(input())
while t > 0:
	n = int(input())
	matrix = []
	for i in range(n):
		row = [int(x) for x in sys.stdin.readline().split()]
		matrix.append(row)
	print(trace(matrix, n))
	t -= 1


t = int(input())
while t:
	t -= 1
	(n,) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append([int(x) for x in input().split()])
	for i in range(n - 1):
		for j in range(n - 1):
			arr[i + 1][j + 1] += arr[i][j]
	ans = -float('inf')
	for i in range(n):
		for j in range(n):
			ans = max(ans, arr[i][j])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	m = []
	for i in range(n):
		r = list(map(int, input().split()))
		m.append(r)
	d = []
	for i in range(n):
		j = 0
		s = 0
		while i < n and j < n:
			s += m[i][j]
			i += 1
			j += 1
		d.append(s)
	for j in range(n):
		i = 0
		s = 0
		while i < n and j < n:
			s += m[i][j]
			i += 1
			j += 1
		d.append(s)
	print(max(d))


import numpy as np
tests = int(input())
for i in range(tests):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	matrix = np.matrix(arr)
	maxi = 0
	for i in range(n - (n + (n - 1)), n):
		if maxi < sum(np.diag(matrix, i)):
			maxi = sum(np.diag(matrix, i))
	print(maxi)


for i in range(int(input())):
	n = int(input())
	m = []
	for i in range(n):
		l = list(map(int, input().split()))
		m.append(l)
	r = []
	for j in range(n):
		k = j
		l = 0
		t = 0
		while k < n:
			t = t + m[l][k]
			r.append(t)
			k = k + 1
			l = l + 1
	for j in range(1, n):
		k = j
		l = 0
		t = 0
		while k < n:
			t = t + m[k][l]
			r.append(t)
			k = k + 1
			l = l + 1
	print(max(r))


for _ in range(int(input())):
	l = int(input())
	A = []
	for __ in range(l):
		A.append(list(map(int, input().split())))
	v = 0
	m = 0
	for r in range(l):
		v = 0
		for c in range(l - r):
			v += A[r + c][c]
		m = max(m, v)
	for c in range(l):
		v = 0
		for r in range(l - c):
			v += A[r][c + r]
		m = max(m, v)
	print(m)


for _ in range(int(input())):
	n = int(input())
	matrix = {}
	for i in range(1, n + 1):
		temp = map(int, input().split())
		matrix[i] = {i: j for (i, j) in enumerate(temp, 1)}
		n1 = n
	maxsum = 0
	while n1 > 1:
		down = sum((matrix[n1 + i - 1][i] for i in range(1, n - n1 + 2)))
		up = sum((matrix[i][n1 + i - 1] for i in range(1, n - n1 + 2)))
		maxsum = max(maxsum, max(down, up))
		n1 -= 1
	diag = sum((matrix[i][i] for i in range(1, n + 1)))
	print(max(maxsum, diag))


for _ in range(int(input())):
	n = int(input())
	A = []
	for i in range(n):
		l = [int(i) for i in input().split()]
		A.append(l)
	maxnum = 0
	for i in range(n):
		x = i
		y = 0
		tsum = 0
		while x < n:
			tsum += A[y][x]
			x += 1
			y += 1
		if tsum > maxnum:
			maxnum = tsum
	for i in range(1, n):
		x = 0
		y = i
		tsum = 0
		while y < n:
			tsum += A[y][x]
			x += 1
			y += 1
		if tsum > maxnum:
			maxnum = tsum
	print(maxnum)


for tc in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	ans = 0
	for i in range(n):
		dsum = 0
		for j in range(n - i):
			dsum += a[i + j][j]
		ans = max(ans, dsum)
	for j in range(n):
		dsum = 0
		for i in range(n - j):
			dsum += a[i][i + j]
		ans = max(ans, dsum)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	t = 0
	for i in range(n):
		(r, s) = (0, 0)
		for j in range(n - i):
			r += a[j][i + j]
			s += a[i + j][j]
		t = max(r, s, t)
	print(t)


tests = int(input())
for i in range(tests):
	n = int(input())
	arr = [0] * (2 * n)
	for j in range(n):
		temp = list(map(int, input().split()))
		for k in range(n):
			arr[n - j + k] += temp[k]
	print(max(arr))


t = int(input())
for _ in range(t):
	n = int(input())
	emp = list()
	for ignore in range(n):
		emp.append(list(map(int, input().split()))[:n])
	traces = list()
	for i in range(n):
		x = 0
		y = i
		sum = 0
		while x < n and y < n:
			sum += emp[x][y]
			x += 1
			y += 1
		traces.append(sum)
	for i in range(1, n):
		x = i
		y = 0
		sum = 0
		while x < n and y < n:
			sum += emp[x][y]
			x += 1
			y += 1
		traces.append(sum)
	print(max(traces))


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for x in range(n):
		x = list(map(int, input().split()))
		a.append(x)
	l = []
	for p in range(n):
		x = p
		y = 0
		t = 0
		while x < n:
			t += a[x][y]
			l.append(t)
			x += 1
			y += 1
	for p in range(1, n):
		x = p
		y = 0
		t = 0
		while x < n:
			t += a[y][x]
			l.append(t)
			x += 1
			y += 1
	print(max(l))


t = int(input())
for i in range(t):
	n = int(input())
	matrix = []
	for j in range(n):
		a = list(map(int, input().split(' ')))
		matrix.append(a)
	final_sum = 0
	for k in range(n):
		sum1 = 0
		sum2 = 0
		for p in range(0, k + 1):
			sum1 += matrix[p][n + p - k - 1]
			sum2 += matrix[n + p - k - 1][p]
		sumo = max(sum1, sum2)
		final_sum = max(sumo, final_sum)
	print(final_sum)


for _ in range(int(input())):
	N = int(input())
	mat = []
	for i in range(N):
		row = list(map(int, input().split()))
		mat.append(row)
	tmx = 0
	for i in range(N):
		(trace1, trace2) = (0, 0)
		for j in range(N - i):
			trace1 += mat[j + i][j]
			trace2 += mat[j][j + i]
		tmx = max(trace1, trace2, tmx)
	print(tmx)


import numpy as np

def read_row():
	return np.array([int(num) for num in input().split()])
for _ in range(int(input().strip())):
	size = int(input().strip())
	A = read_row()
	for k in range(1, size):
		A = np.vstack((A, read_row()))
	high = 0
	for i in range(1 - size, size):
		if np.trace(A, i) > high:
			high = np.trace(A, i)
	print(high)


for _ in range(int(input())):
	n = int(input())
	traces = [0] * (2 * n - 1)
	for row_num in range(n):
		row = list(map(int, input().split()))
		for col_num in range(n):
			traces[col_num - row_num + n - 1] += row[col_num]
	print(max(traces))


from numpy import array, trace
for _ in range(int(input())):
	n = int(input())
	elements = []
	for _ in range(n):
		lst = list(map(int, input().split()))
		elements.extend(lst)
	matrix = array(elements).reshape(n, n)
	res = 0
	for i in range(n):
		for j in range(n):
			s = matrix[i:, j:]
			traced = trace(s)
			if traced > res:
				res = traced
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	mat = []
	for i in range(n):
		l = list(map(int, input().split()))
		mat.append(l)
	ans = []
	for x in range(n - 1, -1, -1):
		s = 0
		for (i, j) in zip(list(range(n)), list(range(x, n))):
			s += mat[i][j]
		ans.append(s)
	for y in range(1, n):
		s1 = 0
		for (i, j) in zip(list(range(y, n)), list(range(n))):
			s1 += mat[i][j]
		ans.append(s1)
	print(max(ans))


for _ in range(int(input())):
	n = int(input())
	m = []
	for i in range(n):
		m.append(list(map(int, input().split())))
	lo = [0 for i in range(n)]
	up = [0 for i in range(n)]
	t = 0
	for i in range(n):
		for j in range(n):
			if i > j:
				lo[i - j] = lo[i - j] + m[i][j]
			elif i < j:
				up[j - i] = up[j - i] + m[i][j]
			else:
				t = t + m[i][j]
	print(max(lo + up + [t]))


t = int(input())
while t > 0:
	n = int(input())
	l = []
	i = 0
	L = []
	while i < n:
		l = l + [list(map(int, input().split()))]
		i = i + 1
	u = 0
	for j in range(0, n):
		k = 0
		while k + j < n:
			u = u + l[k][k + j]
			k = k + 1
		L = L + [u]
		u = 0
	o = 0
	for j in range(0, n):
		k = n - 1
		while n > k - j > -1 and n > k > -1:
			o = o + l[k][k - j]
			k = k - 1
		L = L + [o]
		o = 0
	print(max(L))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		row = list(map(int, input().split()))
		a.append(row)
	sums = []
	for i in range(n):
		(x, y) = (0, i)
		temp = 0
		while x < n and y < n:
			temp += a[x][y]
			x += 1
			y += 1
		sums.append(temp)
	for i in range(n):
		(x, y) = (i, 0)
		temp = 0
		while x < n and y < n:
			temp += a[x][y]
			x += 1
			y += 1
		sums.append(temp)
	print(max(sums))


for i in range(int(input())):
	h = int(input())
	f = []
	ans = []
	for j in range(0, h):
		f.append(list(map(int, input().split())))
	for k in range(0, h):
		sum1 = 0
		sum2 = 0
		for l in range(0, k + 1):
			sum1 += f[l][h + l - k - 1]
			sum2 += f[h + l - k - 1][l]
		ans.append(sum1)
		ans.append(sum2)
	print(max(ans))


for _ in range(int(input())):
	mat = {}
	n = int(input())
	for i in range(n):
		mat[i + 1] = dict(enumerate(map(int, input().split()), start=1))
	s = set()
	for i in range(1, n):
		s.add(sum([mat[x][x + n - i] for x in range(1, i + 1)]))
		s.add(sum([mat[x + n - i][x] for x in range(1, i + 1)]))
	s.add(sum([mat[i][i] for i in range(1, n + 1)]))
	print(max(s))


for _ in range(int(input())):
	n = int(input())
	matrix = [[j for j in map(int, input().split(' '))] for i in range(n)]
	max_trace = 0
	for r in range(n):
		trace1 = 0
		trace2 = 0
		for c in range(n - r):
			trace1 += matrix[r + c][c]
			trace2 += matrix[c][r + c]
		if trace1 > max_trace:
			max_trace = trace1
		if trace2 > max_trace:
			max_trace = trace2
	print(max_trace)


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


t = int(input())
for j in range(t):
	n = int(input())
	m = [[0 for x in range(n)] for x in range(n)]
	for i in range(n):
		m[i] = list(map(int, input().split()))
	s = 0
	for a in range(n):
		s1 = 0
		s2 = 0
		for b in range(n - a):
			s1 += m[a + b][b]
			s2 += m[b][a + b]
		maxx = max(s1, s2)
		if maxx > s:
			s = maxx
	print(s)


from numpy import array, trace
for i in range(int(input())):
	n = int(input())
	a = []
	for j in range(n):
		u = list(map(int, input().split()))
		a.extend(u)
	matrix = array(a).reshape(n, n)
	maxx = 0
	for k in range(n):
		for m in range(n):
			s = matrix[k:, m:]
			traced = trace(s)
			maxx = max(traced, maxx)
	print(maxx)


import numpy as np

def traceSum(matrix, n):
	(sum, round, j) = (0, n - 1, 0)
	i = round
	sumArray = []
	while i >= 0:
		while i < n:
			sum += matrix[i][j]
			i += 1
			j += 1
		round -= 1
		(i, j) = (round, 0)
		sumArray.append(sum)
		sum = 0
	round = n - 1
	(i, j) = (0, round)
	while j > 0:
		while j < n:
			sum += matrix[i][j]
			i += 1
			j += 1
		round -= 1
		(i, j) = (0, round)
		sumArray.append(sum)
		sum = 0
	return max(sumArray)
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for i in range(0, n):
		ele = list(map(int, input().split()))
		a.append(ele)
	matrix = np.array(a).reshape(n, n)
	print(traceSum(matrix, n))


for _ in range(int(input())):
	n = int(input())
	a = []
	for T in range(n):
		a.append([int(x) for x in input().split()])
	s_list = []
	for i in range(n):
		s = 0
		for j in range(n - i):
			s += a[j][i + j]
		s_list.append(s)
	for i in range(1, n):
		s = 0
		for j in range(n - i):
			s += a[i + j][j]
		s_list.append(s)
	print(max(s_list))


n = int(input())
for i in range(n):
	length = int(input())
	matrix = []
	for j in range(length):
		temp = list(map(int, input().split()))
		matrix.append(temp)
	result = set()
	for j in range(length):
		k = j
		l = 0
		temp = 0
		temp2 = 0
		while k < length:
			temp += matrix[l][k]
			temp2 += matrix[k][l]
			k += 1
			l += 1
		result.add(temp)
		result.add(temp2)
	print(max(result))


t = int(input())
for i in range(t):
	n = int(input())
	mat = []
	for j in range(n):
		a = list(map(int, input().split()))
		mat.append(a)
	tr = []
	for j in range(n):
		(x, y) = (0, 0 + j)
		s = 0
		while x < n and y < n:
			s += mat[x][y]
			x += 1
			y += 1
		tr.append(s)
	for j in range(n):
		(x, y) = (0 + j, 0)
		s = 0
		while x < n and y < n:
			s += mat[x][y]
			x += 1
			y += 1
		tr.append(s)
	print(max(tr))


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


for t in range(int(input())):
	l = int(input())
	m = []
	for r in range(l):
		m.append(list(map(int, input().split())))
	maxsum = 0
	for i in range(l):
		s1 = 0
		s2 = 0
		for j in range(i + 1):
			s1 += m[j][l + j - i - 1]
			s2 += m[l + j - i - 1][j]
		if maxsum < s1:
			maxsum = s1
		if maxsum < s2:
			maxsum = s2
	print(maxsum)


import numpy as np
T = int(input())
for k in range(T):
	N = int(input())
	temp = [list(map(int, input().split()))]
	A = np.array(temp)
	for i in range(N - 1):
		temp = [list(map(int, input().split()))]
		A = np.append(A, temp, axis=0)
	T = np.zeros(2 * N - 1)
	for k in range(N):
		T[k] = np.trace(A[0:N - k, k:])
	for k in range(N - 1):
		T[N + k] = np.trace(A[k + 1:, 0:N - k - 1])
	print(int(max(T)))


for t in range(int(input())):
	n = int(input())
	a = [[int(j) for j in input().split()] for i in range(n)]
	ans = 0
	for i in range(n):
		trace = 0
		for j in range(n - i):
			trace += a[i + j][j]
		if trace > ans:
			ans = trace
	for i in range(n):
		trace = 0
		for j in range(n - i):
			trace += a[j][i + j]
		if trace > ans:
			ans = trace
	print(ans)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	a = []
	for x in range(n):
		a.append(list(map(int, input().split())))
	a = np.array(a)
	sums = [a.trace()]
	for x in range(1, n):
		sums.append(a[0:n - x, x:n].trace())
		sums.append(a[x:n, 0:n - x].trace())
	print(max(sums))


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	l = []
	trace = []
	for i in range(n):
		temp = list(map(int, input().split()))
		l.append(temp)
	m = 0
	for i in range(n):
		m += l[i][i]
	trace.append(m)
	for i in range(1, n):
		x = i
		y = 0
		s1 = 0
		s2 = 0
		while x < n and y < n:
			s1 += l[x][y]
			s2 += l[y][x]
			x += 1
			y += 1
		trace.extend([s1, s2])
	print(max(trace))


def trace(l, n):
	maxx = 0
	for i in range(n):
		for j in range(n):
			index = 0
			summ = 0
			while j + index < n and i + index < n:
				summ = summ + l[i + index][j + index]
				index += 1
			if summ > maxx:
				maxx = summ
	return maxx
for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l1 = [int(x) for x in input().split()]
		l.append(l1)
	print(trace(l, n))


T = int(input())
for k in range(0, T):
	N = int(input())
	matrix = []
	for i in range(0, N):
		a = list(map(int, input().split()))
		matrix.append(a)
	max_trace = []
	for i in range(0, N):
		trace1 = 0
		trace2 = 0
		for j in range(0, i + 1):
			trace1 += matrix[j][N + j - i - 1]
			trace2 += matrix[N + j - i - 1][j]
			max_trace.append(trace1)
			max_trace.append(trace2)
	print(max(max_trace))


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		temp = [int(x) for x in input().split()]
		a.append(temp)
	trace = 0
	i = 0
	for j in range(n):
		r = i
		c = j
		m = a[r][c]
		while r < n - 1 and c < n - 1:
			r += 1
			c += 1
			m += a[r][c]
		if m > trace:
			trace = m
	i = 0
	for j in range(1, n):
		r = j
		c = i
		m = a[r][c]
		while r < n - 1 and c < n - 1:
			r += 1
			c += 1
			m += a[r][c]
		if m > trace:
			trace = m
	print(trace)


def trace_of_matrix_v2(matrix):
	_list = []
	for diff in range(len(matrix)):
		(sum1, sum2, index) = (0, 0, diff)
		for i in range(len(matrix) - diff):
			sum1 += matrix[index][i]
			sum2 += matrix[i][index]
			index += 1
		_list.append(sum1)
		_list.append(sum2)
	return max(_list)

def __starting_point():
	t = int(input())
	for _ in range(t):
		n = int(input())
		_list = []
		for _ in range(n):
			_list.append(list(map(int, input().split())))
		print(trace_of_matrix_v2(_list))
__starting_point()


tests = int(input())
for test in range(tests):
	N = int(input())
	a = []
	for row in range(N):
		a.append([int(x) for x in input().split()])
	max_a = []
	for i in range(N):
		max_c = 0
		count = i
		for j in range(N - i):
			if count < N:
				max_c += a[j][count]
			count += 1
		max_a.append(max_c)
	for i in range(N):
		if i == 0:
			continue
		max_c = 0
		count = i
		for j in range(N - i):
			if count < N:
				max_c += a[count][j]
			count += 1
		max_a.append(max_c)
	print(max(max_a))


def matrix(i, j, n):
	sum = 0
	while i < n and j < n:
		sum += L[i][j]
		i += 1
		j += 1
	return sum

def entire(L, n):
	ans = []
	for i in range(n):
		for j in range(n):
			ans.append(matrix(i, j, n))
	return max(ans)
for i in range(int(input())):
	n = int(input())
	L = [list(map(int, input().split())) for k in range(n)]
	print(entire(L, n))


t = int(input())
for tc in range(t):
	x = int(input())
	l = []
	for i in range(x):
		l.append(list(map(int, input().split())))
	ans = 0
	for i in range(x):
		dsum = 0
		for j in range(x - i):
			dsum += l[i + j][j]
		ans = max(ans, dsum)
	for j in range(x):
		dsum = 0
		for i in range(x - j):
			dsum += l[i][i + j]
		ans = max(ans, dsum)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	matrix = []
	for __ in range(n):
		row = list(map(int, input().split()))
		matrix.append(row)
	best = 0
	for i in range(n):
		(r, c) = (0, i)
		t_s = 0
		while c < n:
			t_s += matrix[r][c]
			r += 1
			c += 1
		if best < t_s:
			best = t_s
	for i in range(1, n):
		(r, c) = (i, 0)
		t_s = 0
		while r < n:
			t_s += matrix[r][c]
			r += 1
			c += 1
		if best < t_s:
			best = t_s
	print(best)


for k in range(int(input())):
	max_trace = -1000000
	n = int(input())
	matrix = [list(map(int, input().split())) for m in range(n)]
	for i in range(n):
		s = 0
		for j in range(n - i):
			s += matrix[j][j + i]
		if s > max_trace:
			max_trace = s
	for i in range(n):
		s = 0
		for j in range(n - i):
			s += matrix[j + i][j]
		if s > max_trace:
			max_trace = s
	print(max_trace)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	m = []
	for i in range(0, n):
		arr = list(map(int, input().strip().split()))
		m.append(arr)
	alltraces = []
	for i in range(0, n):
		(x, y) = (0, 0 + i)
		temp = 0
		while x < n and y < n:
			temp += m[x][y]
			x += 1
			y += 1
		alltraces.append(temp)
	for i in range(0, n):
		(x, y) = (0 + i, 0)
		temp = 0
		while x < n and y < n:
			temp += m[x][y]
			x += 1
			y += 1
		alltraces.append(temp)
	print(max(list(set(alltraces))))


T = int(input())
for _ in range(T):
	n = int(input())
	mat = []
	for _ in range(n):
		A = list(map(int, input().split()))
		mat.append(A)
	tmax = 0
	for i in range(n):
		(trace1, trace2) = (0, 0)
		for j in range(n - i):
			trace1 += mat[j + i][j]
			trace2 += mat[j][j + i]
		tmax = max(trace1, trace2, tmax)
	print(tmax)