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: interview

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]
    #print(a)
    for i in range(m):
        for j in range(1, n):
            v[j][i] += v[j-1][i]
    #print(v)
    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
    #print(b,c)
    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]
            #print(b[i])
            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)
        #print(J)
    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])
        # print(x)
        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)
    #print(a,arr)
    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)