[SWEA 2001 python] 파리 퇴치

T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    MAP = []
    for i in range(N):
        MAP.append(list(map(int, input().split())))

    total_map = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            total_map[i][j] = MAP[i - 1][j - 1] + total_map[i - 1][j] + total_map[i][j - 1] - total_map[i - 1][j - 1]

    result = total_map[M][M]
    for i in range(M, N + 1):
        for j in range(M, N + 1):
            total = total_map[i][j] - total_map[i - M][j] - total_map[i][j - M] + total_map[i - M][j - M]
            if total > result:
                result = total

    print('#{} {}'.format(t, result))