Chef has a pepperoni pizza in the shape of a $N \times N$ grid; both its rows and columns are numbered $1$ through $N$. Some cells of this grid have pepperoni on them, while some do not. Chef wants to cut the pizza vertically in half and give the two halves to two of his friends. Formally, one friend should get everything in the columns $1$ through $N/2$ and the other friend should get everything in the columns $N/2+1$ through $N$.
Before doing that, if Chef wants to, he may choose one row of the grid and reverse it, i.e. swap the contents of the cells in the $i$-th and $N+1-i$-th column in this row for each $i$ ($1 \le i \le N/2$).
After the pizza is cut, let's denote the number of cells containing pepperonis in one half by $p_1$ and their number in the other half by $p_2$. Chef wants to minimise their absolute difference. What is the minimum value of $|p_1-p_2|$?

-----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 a string with length $N$ describing the $i$-th row of the grid; this string contains only characters '1' (denoting a cell with pepperonis) and '0' (denoting a cell without pepperonis).

-----Output-----
For each test case, print a single line containing one integer — the minimum absolute difference between the number of cells with pepperonis in the half-pizzas given to Chef's friends.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 1,000$
- $N$ is even
- the sum of $N \cdot N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
2
6
100000
100000
100000
100000
010010
001100
4
0011
1100
1110
0001

-----Example Output-----
2
0

-----Explanation-----
Example case 1: Initially, $|p_1-p_2| = 4$, but if Chef reverses any one of the first four rows from "100000" to "000001", $|p_1-p_2|$ becomes $2$.
Example case 2: Initially, $|p_1-p_2| = 0$. We cannot make that smaller by reversing any row.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l1=[]
 l2=[]
 
 for i in range(n):
  s=input()
  a=s[ :n//2].count('1')
  b=s[n//2: ].count('1')
  if a>b:
   l1.append(a-b)
   
  elif a<b:
   l2.append(b-a)
   
 p=sum(l1)
 q=sum(l2)
 
 if p==q:
  print(0)
  
 elif p>q:
  diff=p-q
  flag=0
  for i in range(diff//2, 0, -1):
   a=diff-i
   if (i in l1) or (a in l1):
    print(abs(a-i))
    flag=1
    break
   
  if flag==0:
   print(diff)
   
 else:
  diff=q-p
  flag=0
  for i in range(diff//2, 0, -1):
   a=diff-i
   if (i in l2) or (a in l2):
    print(abs(a-i))
    flag=1
    break
   
  if flag==0:
   print(diff)

t=int(input())
for i in range(t):
 n=int(input())
 a=[]
 c1=0
 c2=0
 for i in range(n):
  s=input()
  a.append([s[0:n//2].count("1"),s[n//2:].count("1")])
  c1+=a[i][0]
  c2+=a[i][1]
 tp1=c1
 tp2=c2
 m=abs(c1-c2)
 for i in range(n):
  tp1+=a[i][1]
  tp1-=a[i][0]
  tp2+=a[i][0]
  tp2-=a[i][1]
  if(m>abs(tp1-tp2)):
   m=abs(tp1-tp2)
  tp1=c1
  tp2=c2
 print(m)
  
  
   
  
  
  
 
 
 
  


def row(alist):
 a,n=0,len(alist)
 for i in range(n//2):
  if alist[i]=='1':
   a+=1
 for i in range(n//2,n):
  if alist[i]=='1':
   a-=1
 return(a)
t=int(input())
for count in range(t):
 n=int(input())
 mat=[input() for i in range(n)]
 A=[]
 for i in range(n):
  A.append(row(mat[i]))
 s=sum(A)
 B=[abs(s)]
 if s>0:
  for i in range(n):
   if A[i]>0:
    B.append(abs(s-2*A[i]))
 else:
  for i in range(n):
   if A[i]<0:
    B.append(abs(s-2*A[i]))
 print(min(B))

for _ in range(int(input())):
 n=int(input())
 aux=[0]*n
 tot=0
 for i in range(n):
  s=list(map(int,list(input())))
  aux[i]=sum(s[:n//2])-sum(s[n//2:])
 tot=sum(aux)
 if tot==0:
  print(0)
 else:
  x=[]
  for i in range(len(aux)):
   x.append(abs(tot-(2*aux[i])))
  print(min(x))

for t in range(int(input())):
 n=int(input())
 p1=0
 p2=0
 ans=500
 diff=[]
 for i in range(n):
  a=input()
  x=0
  y=0
  for j in range(n//2):
   if a[j]=='1':
    p1+=1
    x+=1
  for j in range(n//2,n):
   if a[j]=='1':
    p2+=1
    y+=1
  diff.append(2*(y-x))
 for k in range(n):
  ans=min(ans,abs(p1-p2+diff[k]))
 print(min(ans,abs(p1-p2)))
 


for t in range(int(input())):
 n=int(input())
 matrix=[]
 ans=500
 p1=0
 p2=0
 diff=[]
 for i in range(n):
  num=[]
  a=input()
  x=0
  y=0
  for j in range(n//2):
   num.append(int(a[j]))
   if a[j]=='1':
    p1+=1
    x+=1
  for j in range(n//2,n):
   num.append(int(a[j]))
   if a[j]=='1':
    p2+=1
    y+=1
  diff.append(2*(y-x))
  matrix.append(num)
 for k in range(n):
  ans=min(ans,abs(p1-p2+diff[k]))
 print(min(ans,abs(p1-p2)))
 


# cook your dish here
test=int(input())
for i in range(test):
 n=int(input())
 a=[]
 p1=p2=0
 for j in range(n):
  s=input()
  a.append([s[:n//2].count('1'),s[n//2:].count('1')])
  p1+=a[j][0]
  p2+=a[j][1]
 m=abs(p1-p2)
 tp2=p2
 tp1=p1
 for j in range(n):
  tp1-=a[j][0]
  tp1+=a[j][1]
  tp2-=a[j][1]
  tp2+=a[j][0]
  if m>abs(tp1-tp2):
   m=abs(tp1-tp2)
  tp1=p1
  tp2=p2
 print(m)


for i in range(int(input())):
 n=int(input())
 a=[]
 p1=p2=0
 for j in range(n):
  s=input()
  a.append([s[:n//2].count('1'),s[n//2:].count('1')])
  p1+=a[j][0]
  p2+=a[j][1]
 m=abs(p1-p2)
 tp2=p2
 tp1=p1
 for j in range(n):
  tp1-=a[j][0]
  tp1+=a[j][1]
  tp2-=a[j][1]
  tp2+=a[j][0]
  if m>abs(tp1-tp2):
   m=abs(tp1-tp2)
  tp1=p1
  tp2=p2
 print(m)


for i in range(int(input())):
 n=int(input())
 a=[]
 p1=p2=0
 for j in range(n):
  s=input()
  a.append([s[:n//2].count('1'),s[n//2:].count('1')])
  p1+=a[j][0]
  p2+=a[j][1]
 m=abs(p1-p2)
 tp2=p2
 tp1=p1
 for j in range(n):
  tp1-=a[j][0]
  tp1+=a[j][1]
  tp2-=a[j][1]
  tp2+=a[j][0]
  if m>abs(tp1-tp2):
   m=abs(tp1-tp2)
  tp1=p1
  tp2=p2
 print(m)


t=int(input())
for _ in range(t):
 n=int(input())
 lr=[0]*n
 for i in range(n):
  s=input()
  lr[i]=s[:n//2].count("1")-s[n//2:].count("1")
 lrsum=sum(lr)

 if(lrsum==0):
  print("0")

 else:
  x=[abs(lrsum-2*lr[i]) for i in range(n)]
  print(min(x))




t=int(input())
for _ in range(t):
 n=int(input())
 l=[0]*n
 r=[0]*n
 for i in range(n):
  s=input()
  l[i]=s[:n//2].count("1")
  r[i]=s[n//2:].count("1")
  if(l[i]>r[i]):
   l[i]=l[i]-r[i]
   r[i]=0
  elif(l[i]==r[i]):
   l[i]=0
   r[i]=0
  else:
   r[i]=r[i]-l[i]
   l[i]=0
 lsum=sum(l)
 rsum=sum(r)
 x=abs(lsum-rsum)
 if(x==0):
  print("0")

 else:
  m=1000000000000000
  if(lsum>rsum):
   for j in range(n):
    k=abs(x-2*l[j])
    if(k<m):
     m=k
     if(m==0):
      break
  elif (rsum > lsum):
   for j in range(n):
    k = abs(x - 2 * r[j])
    if (k < m):
     m = k
     if (m == 0):
      break
  print(m)




# cook your dish here

for _ in range(int(input())):
 n=int(input())
 l=[]
 for i in range(n):
  a=input()
  l.append(a)
 x=0
 y=0
 p=0
 q=0
 li=[]
 for i in range(n):
  p=0
  q=0
  for j in range(n):
   if j<(n/2) and l[i][j]=="1":
    x+=1
    p+=1
   elif j>=(n/2) and l[i][j]=="1":
    y+=1
    q+=1
  a=[]
  a=(p,q)
  li.append(a)
 mi=abs(x-y)
 if x-y==0:
  print(x-y)
 else:
  mi=abs(x-y)
  d=x-y
  for i in range(n):
   c=x-li[i][0]+li[i][1]
   b=y+li[i][0]-li[i][1]
   z=abs(c-b)
   if mi>abs(z):
    mi=abs(z)
  print(mi)


t = int(input())
for i in range(t):
 diff = []
 n = int(input())
 for j in range(n):
  c1 = 0
  c2 = 0
  l1 = list(map(int,input()))
  for k in range(n):
   if l1[k] == 1 and k < n//2:
    c1 += 1
   elif l1[k] and k >= n//2:
    c2 += 1
  diff.append(c1-c2)
 # print(diff)
 current_diff = sum(diff)
 # print(current_diff)
 new = []
 for kk in range(len(diff)):
  new.append(abs(current_diff - 2*diff[kk]))
 print(min(min(new),abs(current_diff)))



t=int(input())
for you in range(t):
 n=int(input())
 lo=[]
 for i in range(n):
  l=input()
  li=[int(i) for i in l]
  lo.append(li)
 lrowhalf1=[0 for i in range(n)]
 lrowhalf2=[0 for i in range(n)]
 
 for i in range(n):
  lrowhalf1[i]=sum(lo[i][0:n//2])
  lrowhalf2[i]=sum(lo[i][n//2:n])
 
 mina=abs(sum(lrowhalf1)-sum(lrowhalf2))
 for i in range(n):
  mini=abs(sum(lrowhalf1)-2*(lrowhalf1[i]-lrowhalf2[i])-sum(lrowhalf2))
  if(mini<mina):
   mina=mini
 print(mina)

for _ in range(int(input())):
 n=int(input())
 left=0
 right=0
 Dict={}
 for i in range(n):
  s=input()
  curr_left=s[0:n//2].count("1")
  curr_right=s[n//2:n].count("1")
  left+=curr_left
  right+=curr_right
  Dict[i]=curr_left-curr_right
 ans=abs(left-right)
 org_ans=left-right

 for i in range(n):
  ans=min(ans,abs(org_ans-2*Dict[i]))
 print(ans)

# cook your dish here
T = int(input())
for _ in range(T):
 N = int(input())
 mini = 10000000
 count1,count2=0,0
 u = []
 save = []
 for i in range(N):
  a = input()
  u.append(a)
  x = a[:N//2].count('1')
  y = a[N//2:].count('1')
  count1+=x
  count2+=y
  save.append(x-y)
 if(count1==count2):
  print(0)
  continue
 for i in save:
  mini = min(abs(count1-2*i-count2),mini)
 print(mini)
 



for _ in range(int(input())):
 N = int(input())
 array = []
 for i in range(N):
  a = input()
  first = 0
  second = 0
  for j in range(N//2):
   first += int(a[j])
  for j in range(N//2,N):
   second += int(a[j])
  array.append([first,second])
 sm1 = 0
 sm2 = 0
 for i in array:
  sm1 += i[0]
  sm2 += i[1]
 diff = abs(sm1 - sm2)
 for i in array:
  diff = min(diff, abs(sm1 - sm2 - i[0] * 2 + i[1] * 2))
 print(diff)

# cook your dish here
for __ in range(int(input())):
 n=int(input());a=[];ans=10**9;
 for _ in range(n):
  a.append(list(input()))
 l1,l2,acnt,bcnt,diff=[],[],0,0,[];
 for i in range(n):
  acnt,bcnt=0,0;
  for j in range(len(a[i])//2):
   if(a[i][j]=='1'):acnt+=1
   if(a[i][n-1-j]=='1'):bcnt+=1
  l1.append(acnt)
  l2.append(bcnt)
 acnt,bcnt=sum(l1),sum(l2);
 if(acnt==bcnt):print("0")
 elif(abs(bcnt-acnt)==1):print("1")
 else:
  if(bcnt>acnt):
   l1,l2=l2,l1
   acnt,bcnt=bcnt,acnt
  for i in range(n):
   val=l1[i]-l2[i]
   diff.append(val if(val>0) else 0)
  for i in range(len(diff)):
   ans=min(ans,abs(acnt-diff[i]-bcnt-diff[i]))
  print(ans)


t = int(input())

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

 row_count = {}

 for i in range(n):
  s = input()
  row_count[i+1] = [s[:(n//2)].count('1'), s[(n//2):].count('1')]

 left_sum, right_sum = 0, 0
 for val in list(row_count.values()):
  left_sum += val[0]
  right_sum += val[1]

 min_abs_diff = abs(left_sum - right_sum)

 for row, val in list(row_count.items()):
  diff_swap_row = abs(
   (left_sum - val[0] + val[1]) - (right_sum - val[1] + val[0]))
  if diff_swap_row < min_abs_diff:
   min_abs_diff = diff_swap_row

 print(min_abs_diff)


for T in range(int(input())):
 N=int(input())
 P=[0]*N
 Q=[0]*N
 R=[0]*N
 X=N//2
 for I in range(N):
  P[I]=input()
 for I in range(N):
  for J in range(X):
   if P[I][J]=='1':
    Q[I]+=1
   if P[I][J+X]=='1':
    R[I]+=1
 S=sum(Q)-sum(R)
 Z={abs(S)}
 for I in range(N):
  if Q[I]!=R[I]:
   Z.add(abs((S+2*(R[I]-Q[I]))))
 print(min(Z))