Every college has a stud−max$stud-max$ buoy. JGEC$JGEC$ has its own Atul$Atul$ who loves to impress everyone with his smile. A presentation is going on at the auditorium where there are N$N$ rows of M$M$ chairs with people sitting on it. Everyone votes for Atul's presentation skills, but Atul is interested in knowing the maximum$maximum$ amount of vote that he receives either taking K$K$ people vertically$vertically$ or horizontally$horizontally$. Atul$Atul$, however, wants to finish up the presentation party soon, hence asks for your help so that he can wrap up things faster.  

-----Input:-----
- First line will contain T$T$, number of test cases. Then the test cases follow. 
- Each testcase contains of a single line of input, three integers N$N$, M$M$ and K$K$.  
- N lines follow, where every line contains M numbers$numbers$ denoting the size of the sugar cube

-----Output:-----
For each test case, output in a single line the maximum votes Atul can get. 

-----Constraints-----
- 1≤T≤$1 \leq T \leq $5
- 1≤N,M≤500$1 \leq N,M \leq 500$
- K≤min(N,M)$K \leq min(N,M)$ 
- 1≤numbers≤109$1 \leq numbers \leq 10^9$

-----Sample Input:-----
1
4 4 3 
1 4 5 7 
2 3 8 6
1 4 8 9 
5 1 5 6 

-----Sample Output:-----
22

-----EXPLANATION:-----
If Atul starts counting votes from (1,4), then he can take the 3 consecutive elements vertically downwards and those are 7,6 and 9 which is the maximum sum possible.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
for i in range(t):
	q = input().split()
	n = int(q[0])
	m = int(q[1])
	k = int(q[2])
	sumax = 0
	b = []
	for j in range(n):
		a = [int(k) for k in input().split()]
		b = b + [a]
	for j in range(n):
		su = 0
		for x in range(k):
			su = su + b[j][x]
			if su > sumax:
				sumax = su
		for a in range(1, m - k + 1):
			su = su - b[j][a - 1] + b[j][k + a - 1]
			if su > sumax:
				sumax = su
	for j in range(m):
		su = 0
		for x in range(k):
			su = su + b[x][j]
			if su > sumax:
				sumax = su
		for a in range(1, n - k + 1):
			su = su - b[a - 1][j] + b[a + k - 1][j]
			if su > sumax:
				sumax = su
	print(sumax)


for T in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	v = [[0 for x in range(m)] for x in range(n)]
	for i in range(n):
		v[i] = a[i].copy()
	for i in range(n):
		for j in range(1, m):
			a[i][j] += a[i][j - 1]
	for i in range(m):
		for j in range(1, n):
			v[j][i] += v[j - 1][i]
	maxx = 0
	for i in range(n):
		for j in range(k - 1, m):
			if j == k - 1:
				maxx = max(maxx, a[i][j])
			else:
				maxx = max(maxx, a[i][j] - a[i][j - k])
	for i in range(m):
		for j in range(k - 1, n):
			if j == k - 1:
				maxx = max(maxx, v[j][i])
			else:
				maxx = max(maxx, v[j][i] - v[j - k][i])
	print(maxx)


t = int(input())
for z in range(t):
	(n, m, k) = list(map(int, input().split()))
	a = [[0] * m for i in range(n)]
	for i in range(n):
		a[i] = list(map(int, input().split()))
	s2 = 0
	for i in range(n):
		s3 = 0
		co = 0
		for j in range(0, m):
			if co == k:
				s3 = s3 + a[i][j] - a[i][j - k]
			else:
				s3 = s3 + a[i][j]
				co += 1
			if s3 > s2:
				s2 = s3
	s3 = 0
	s4 = 0
	for i in range(m):
		s3 = 0
		co = 0
		for j in range(0, n):
			if co == k:
				s3 = s3 + a[j][i] - a[j - k][i]
			else:
				s3 = s3 + a[j][i]
				co += 1
			if s3 > s2:
				s2 = s3
	print(s2)


for t in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = []
	for i in range(n):
		a.append(list(map(int, input().split(' '))))
	max = 0
	b = [0 for i in range(n)]
	c = [0 for i in range(m)]
	for i in range(n):
		b[i] = sum(a[i][:k])
		if b[i] > max:
			max = b[i]
	for i in range(m):
		g = 0
		for x in range(k):
			g = g + a[x][i]
		c[i] = g
		if g > max:
			max = g
	for i in range(n):
		for j in range(1, m - k + 1):
			b[i] = b[i] + a[i][j + k - 1] - a[i][j - 1]
			if b[i] > max:
				max = b[i]
	for i in range(m):
		for j in range(1, n - k + 1):
			c[i] = c[i] + a[j + k - 1][i] - a[j - 1][i]
			if c[i] > max:
				max = c[i]
	print(max)


import numpy as np

def s(arr, n, m, k):
	max_sum = 0
	for i in range(n):
		prev_sum = 0
		curr_sum = 0
		for a in range(k):
			curr_sum += arr[i][a]
		prev_sum = curr_sum
		if max_sum < prev_sum:
			max_sum = prev_sum
		j = 1
		while j + k <= m:
			curr_sum = prev_sum - arr[i][j - 1] + arr[i][j + k - 1]
			prev_sum = curr_sum
			if max_sum < prev_sum:
				max_sum = prev_sum
			j += 1
	return max_sum
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	ans = s(arr, n, m, k)
	arr = np.array(arr)
	arr = arr.T
	l = []
	for i in range(m):
		l.append(list(arr[i]))
	temp = s(l, m, n, k)
	if ans < temp:
		ans = temp
	print(ans)


def maxSum(arr, n, k):
	res = 0
	for i in range(k):
		res += arr[i]
	curr_sum = res
	for i in range(k, n):
		curr_sum += arr[i] - arr[i - k]
		res = max(res, curr_sum)
	return res
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	ma = 0
	J = []
	for i in range(n):
		a = [int(x) for x in input().split()]
		s1 = maxSum(a, m, k)
		if ma < s1:
			ma = s1
		J.append(a)
	for i in range(m):
		arr = [x[i] for x in J]
		ss = maxSum(arr, n, k)
		if ma < ss:
			ma = ss
	print(ma)


t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	main = []
	for i in range(n):
		l = list(map(int, input().split()))
		main.append(l)
	maxi = 0
	for i in range(n):
		q = main[i]
		sum1 = sum(q[0:k])
		i = 0
		j = k - 1
		while j < m:
			if maxi < sum1:
				maxi = sum1
			j += 1
			if j < m:
				sum1 += q[j]
			i += 1
			sum1 -= q[i - 1]
	new = []
	for i in range(m):
		l = [0] * n
		new.append(l)
	for i in range(n):
		for j in range(m):
			new[j][i] = main[i][j]
	for i in range(m):
		q = new[i]
		sum1 = sum(q[0:k])
		i = 0
		j = k - 1
		while j < n:
			if maxi < sum1:
				maxi = sum1
			j += 1
			if j < n:
				sum1 += q[j]
			i += 1
			sum1 -= q[i - 1]
	print(maxi)


t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().strip().split()))
	a = list()
	for i in range(n):
		b = list(map(int, input().strip().split()))
		a.append(b)
	(sm1, sm2) = (0, 0)
	for i in range(n):
		for j in range(k):
			sm2 += a[i][j]
		if sm2 > sm1:
			sm1 = sm2
		for j in range(k, m):
			sm2 += a[i][j] - a[i][j - k]
			if sm2 > sm1:
				sm1 = sm2
		sm2 = 0
	for i in range(m):
		for j in range(k):
			sm2 += a[j][i]
		if sm2 > sm1:
			sm1 = sm2
		for j in range(k, n):
			sm2 += a[j][i] - a[j - k][i]
			if sm2 > sm1:
				sm1 = sm2
		sm2 = 0
	print(sm1)


t = int(input().strip())
for p in range(t):
	(n, m, k) = input().strip().split()
	(n, m, k) = (int(n), int(m), int(k))
	arr = []
	rmax = []
	cmax = []
	for i in range(n):
		arr2 = list(map(int, input().strip().split()))
		arr.append(arr2)
		row_sum = []
		row_sum.append(sum(arr2[:k]))
		for j in range(1, m - k + 1):
			row_sum.append(row_sum[j - 1] - arr2[j - 1] + arr2[j + k - 1])
		rmax.append(max(row_sum))
	for i in range(m):
		col_sum = []
		s = 0
		for j in range(k):
			s += arr[j][i]
		col_sum.append(s)
		for j in range(1, n - k + 1):
			col_sum.append(col_sum[j - 1] - arr[j - 1][i] + arr[j + k - 1][i])
		cmax.append(max(col_sum))
	print(max(max(rmax), max(cmax)))


t = int(input())
for tt in range(t):
	(n, m, k) = map(int, input().split())
	k -= 1
	arr = []
	for i in range(n):
		l = list(map(int, input().split()))
		arr.append(l)
	mm = 0
	for i in range(n):
		x = [0] * len(arr[i])
		x[0] = arr[i][0]
		for j in range(1, m):
			x[j] = x[j - 1] + arr[i][j]
		for j in range(m):
			if j + k < m:
				if j > 0:
					mm = max(mm, x[j + k] - x[j - 1])
				else:
					mm = max(mm, x[j + k])
	for i in range(m):
		x = []
		for j in range(n):
			x.append(arr[j][i])
		y = [0] * n
		y[0] = x[0]
		for j in range(1, n):
			y[j] = y[j - 1] + x[j]
		for j in range(n):
			if j + k < n:
				if j > 0:
					mm = max(mm, y[j + k] - y[j - 1])
				else:
					mm = max(mm, y[j + k])
	print(mm)


t = int(input())
for ii in range(t):
	(n, m, k) = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		pp = [int(x) for x in input().split()]
		a.append(pp)
	arr = []
	for i in range(m):
		pp = []
		for j in range(n):
			pp.append(a[j][i])
		arr.append(pp)
	s = 0
	for i in a:
		for j in range(m - k + 1):
			s = max(s, sum(i[j:j + k]))
	for i in arr:
		for j in range(n - k + 1):
			s = max(s, sum(i[j:j + k]))
	print(s)