You are given a matrix with $n$ rows (numbered from $1$ to $n$) and $m$ columns (numbered from $1$ to $m$). A number $a_{i, j}$ is written in the cell belonging to the $i$-th row and the $j$-th column, each number is either $0$ or $1$.

A chip is initially in the cell $(1, 1)$, and it will be moved to the cell $(n, m)$. During each move, it either moves to the next cell in the current row, or in the current column (if the current cell is $(x, y)$, then after the move it can be either $(x + 1, y)$ or $(x, y + 1)$). The chip cannot leave the matrix.

Consider each path of the chip from $(1, 1)$ to $(n, m)$. A path is called palindromic if the number in the first cell is equal to the number in the last cell, the number in the second cell is equal to the number in the second-to-last cell, and so on.

Your goal is to change the values in the minimum number of cells so that every path is palindromic.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 200$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 30$) — the dimensions of the matrix.

Then $n$ lines follow, the $i$-th line contains $m$ integers $a_{i, 1}$, $a_{i, 2}$, ..., $a_{i, m}$ ($0 \le a_{i, j} \le 1$).


-----Output-----

For each test case, print one integer — the minimum number of cells you have to change so that every path in the matrix is palindromic.


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

Output
0
3
4
4



-----Note-----

The resulting matrices in the first three test cases: $\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}$  $\begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}$  $\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
    n,m = list(map(int, input().split()))
    l = []
    for _ in range(n):
        l.append(list(map(int,input().split())))
    zeroes = [0] * (m + n - 1)
    ones = [0] * (m + n - 1)

    for i in range(n):
        for j in range(m):
            if l[i][j] == 0:
                zeroes[i + j] += 1
            else:
                ones[i + j] += 1

    out = 0

    for i in range((m + n - 1)//2):
        z = zeroes[i] + zeroes[m + n - 2 - i]
        o = ones[i] + ones[m + n - 2 - i]
        out += min(o,z)
    print(out)
                       


import sys

readline = sys.stdin.readline
read = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w = nm()
    a = [nl() for _ in range(h)]
    d = dict()
    for i in range(h):
        for j in range(w):
            v = min(i+j, h+w-2-i-j)
            if v not in d:
                d[v] = [0, 0]
            d[v][a[i][j]] += 1
    ans = 0
    for x in d:
        if x * 2 != h + w - 2:
            ans += min(d[x])
    print(ans)
    return


# solve()

T = ni()
for _ in range(T):
    solve()


def solve():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dc = [[0, 0] for _ in range(0 + 0, n - 1 + m - 1 + 1)]
    for i in range(n):
        for j in range(m):
            dc[i + j][a[i][j]] += 1
    ans = 0
    for i in range(len(dc) // 2):
        j = len(dc) - 1 - i
        ans += min(dc[i][0] + dc[j][0], dc[i][1] + dc[j][1])
    print(ans)

t = int(input())
for _ in range(t):
    solve()

import sys

input=sys.stdin.readline

for _ in range(int(input())):
    n,m=map(int,input().split())
    one=[0]*(n+m-1)
    zero=[0]*(n+m-1)
    for i in range(n):
        a=list(map(int,input().split()))
        for j in range(m):
            one[i+j]+=(a[j]==1)
            zero[i+j]+=(a[j]==0)

    res=0
    for i in range((n+m-1)//2):
        s=one[i]+one[n+m-2-i]
        t=zero[i]+zero[n+m-2-i]
        res+=min(s,t)
    print(res)

import sys
input = sys.stdin.readline
from collections import Counter

t=int(input())
for tests in range(t):
    n,m=list(map(int,input().split()))
    M=[list(map(int,input().split())) for i in range(n)]

    A=[[] for i in range(n+m-1)]

    for i in range(n):
        for j in range(m):
            A[i+j].append(M[i][j])

    ANS=0

    for k in range((n+m-1)//2):
        C=Counter(A[k]+A[-k-1])
        ANS+=min(C[0],C[1])

    print(ANS)

    
    
    


import sys
input = sys.stdin.readline
for f in range(int(input())):
    n,m=map(int,input().split())
    ones=[0]*((n+m)//2)
    for i in range(n):
        line=list(map(int,input().split()))
        for j in range(m):
            x=i+j
            if x>(n+m-2)//2:
                x=n+m-2-x
            if line[j]==1:
                ones[x]+=1
    sol=0
    for i in range((n+m-1)//2):
        tot=2*min(i+1,n,m)
        sol+=min(ones[i],tot-ones[i])
    print(sol)

t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(n)]
    k = [0] * (n + m - 1)
    c = [0] * (n + m - 1)
    for i in range(n):
        for j in range(m):
            c[i + j] += 1
            if a[i][j] == 1:
                k[i + j] += 1
    ans = 0
    for i in range((n + m - 1) // 2):
        j = n + m - 2 - i
        ans += min(k[i] + k[j], c[i] + c[j] - k[i] - k[j])
    print(ans)


T = int(input())
for _ in range(T):
    N,M = list(map(int,input().split()))
    A = [list(map(int,input().split())) for i in range(N)]
    L = N+M-1
    c0 = [0]*L
    c1 = [0]*L
    for i,row in enumerate(A):
        for j,a in enumerate(row):
            if a==0:
                c0[i+j] += 1
            else:
                c1[i+j] += 1
    M = L//2
    ans = 0
    for i in range(M):
        a0 = c0[i] + c0[-1-i]
        a1 = c1[i] + c1[-1-i]
        ans += min(a0,a1)
    print(ans)


T = int(input())
for __ in range(T):
    n, m = map(int, input().split())
    A = []
    for __ in range(n):
        A.append(list(map(int, input().split())))
    D = [[0, 0] for __ in range(n + m - 1)]
    for i in range(n):
        for j in range(m):
            D[i + j][A[i][j]] += 1
    ans = 0
    for k1 in range((n + m - 1) // 2):
        k2 = (n + m - 2) - k1
        x = min(D[k1][0] + D[k2][0], D[k1][1] + D[k2][1])
        ans += x
        # print(k1, k2, x)
    # print(D)
    print(ans)

import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    a = [list(map(int, input().split())) for i in range(n)]
    ptn = n + m - 2
    cnt = 0
    ans = []
    for length in range(n + m + 10):
        tmp = []
        for i in range(length + 1):
            j = length - i
            if 0 <= i < n and 0 <= j < m:
                tmp.append(a[i][j])
        if tmp:
            ans.append(tmp)
            
    len_ans = len(ans)
    res = 0
    for i in range(len_ans // 2):
        cnt = [0, 0]
        for val in ans[i]:
            cnt[val] += 1
        for val in ans[- i - 1]:
            cnt[val] += 1
        res += min(cnt)
    print(res)

      


for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    allCnts = []
    for k in range(n+m-1):
        cnt = [0,0]
        i = k+1
        for j in range(n+m):
            i -= 1
            if i < 0 or i >= n or j >= m:
                continue
            cnt[a[i][j]] += 1
        allCnts.append(cnt)
    for i in range(len(allCnts) // 2):
        zeros = allCnts[i][0] + allCnts[-i-1][0]
        ones = allCnts[i][1] + allCnts[-i-1][1]
        ans += min(zeros, ones)
    print(ans)


t = int(input())
for _ in range(t):
    n,m = list(map(int, input().split(' ')))
    M = []
    for i in range(n):
        M.append(list(map(int, input().split(' '))))
    lo = 0
    hi = n+m-2
    total = 0
    while True:
        if lo >= hi:
            break
        num1 = 0
        num0 = 0
        for i in range(lo+1):
            j = lo-i
            if i<n and j<m and j>=0:
                if M[i][j] == 1:
                    num1+=1
                else:
                    num0+=1
        for i in range(hi+1):
            j = hi-i
            if i<n and j<m and j>=0:
                if M[i][j] == 1:
                    num1+=1
                else:
                    num0+=1
        total += min(num0,num1)
        lo += 1
        hi -= 1
    print(total)







from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

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

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

q= nn()

for _ in range(q):
	n, m = mi()

	mat= []
	for i in range(n):
		row = lm()
		mat.append(row)
	zeros = [0]*(n+m-1)
	ones = [0]*(n+m-1)
	for i in range(n):
		for j in range(m):
			if mat[i][j]==1:
				ones[i+j]+=1
			else:
				zeros[i+j]+=1
	ops= 0
	#print(ones, zeros)
	for i in range((m+n-1)//2):
		ops+= min(zeros[i]+zeros[-i-1], ones[i]+ones[-i-1])

	print(ops)


import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
for _ in range(t):
  n,m=list(map(int,input().split()))
  Z=[0]*(n+m-1)
  O=[0]*(n+m-1)
  for i in range(n):
    A=[int(j) for j in input().split()]
    for j,a in enumerate(A):
      if a==0:
        Z[i+j]+=1
      else:
        O[i+j]+=1
  ans=0
  for i in range((n+m-1)//2):
    x,y=Z[i]+Z[n+m-2-i],O[i]+O[n+m-2-i]
    ans+=min(x,y)
  print(ans)





tt = int(input())

for loop in range(tt):

    n,m = list(map(int,input().split()))

    z = [0] * ((n+m-1)//2)
    o = [0] * ((n+m-1)//2)

    for i in range(n):

        a = list(map(int,input().split()))

        for j in range(m):

            d = min(i+j, n-i-1 + m-j-1)
            if d < len(z):

                if a[j] == 0:
                    z[d] += 1
                else:
                    o[d] += 1

    ans = 0
    for i in range(len(z)):
        ans += min(o[i],z[i])
    print (ans)


t=int(input())
for _ in range(t):
    n,m=map(int,input().split())
    cost=0
    a=[]
    for i in range(n):
        c=list(map(int,input().split()))
        a.append(c)
    r=(n+m-1)//2
    if (r+1)*2<=n+m-1:
        r+=1
    for i in range(r):
        Q=i
        counter0=0
        counter1=0
        for j in range(Q+1):
            if j>=m:
                continue
            if Q-j>=n:
                continue
            if a[Q-j][j]==0:
                counter0+=1
            else:
                counter1+=1
        Q=n+m-2-i
        for j in range(Q+1):
            if j>=m:
                continue
            if Q-j>=n:
                continue
            if a[Q-j][j]==0:
                counter0+=1
            else:
                counter1+=1
        cost+=min(counter0,counter1)
    print(cost)

tests = int (input())
for test in range (tests):
  rows, cols = list(map (int, input().split()))
  a = []
  for i in range (rows):
    b = list(map (int, input().split()))
    a.append (b)
  cnt = [[0 for j in range (2)] for i in range (rows + cols)]
  for r in range (rows):
    for c in range (cols):
      if r + c != rows + cols - r - c - 2:
        cnt[min (r + c, rows + cols - r - c - 2)][a[r][c]] += 1
  res = 0
  for i in cnt:
      res += min (i[0], i[1])
  print (res) 


for _ in range(int(input())):
    A = []
    C = []
    n, m = list(map(int, input().split()))
    for i in range(n):
        B = list(map(int, input().split()))
        A.append(B)
    for i in range((n + m - 1)):
        C.append([])
        for j in range(i + 1):
            if (i - j) < n and j < m:
                C[-1].append(A[i - j][j])
    Ans = 0
    #print(C)
    for i in range(len(C) // 2):
        Ans += min( sum(C[i]) + sum(C[- i - 1]), len(C[i]) + len(C[-1 - i]) - sum(C[i]) - sum(C[- i - 1]))
    print(Ans)



for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    arr = [[0] * m for i in range(n)]
    for i in range(n):
        arr[i] = list(map(int, input().split()))
    ans = 0
    brr = []
    for s in range(n + m - 1):
        kek = [0, 0]
        for i in range(n):
            j = s - i
            if not 0 <= j < m:
                continue
            kek[arr[i][j]] += 1
        brr.append(kek)
    for i in range(len(brr) // 2):
        ans += min(brr[i][0] + brr[-i - 1][0],
                   brr[i][1] + brr[-i - 1][1])
    # if len(brr) % 2 == 1:
    #     ans += min(brr[len(brr) // 2])
    print(ans)