It is well-known that the elephants are afraid of mouses. The Little Elephant from the Zoo of Lviv is not an exception.

The Little Elephant is on a board A of n rows and m columns (0-based numeration). At the beginning he is in cell with coordinates (0; 0) and he wants to go to cell with coordinates (n-1; m-1). From cell (x; y) Little Elephant can go either to (x+1; y) or (x; y+1).

Each cell of the board contains either 1 or 0. If A[i][j] = 1, then there is a single mouse in cell (i; j). Mouse at cell (i; j) scared Little Elephants if and only if during the path there was at least one such cell (x; y) (which belongs to that path) and |i-x| + |j-y| <= 1.

Little Elephant wants to find some correct path from (0; 0) to (n-1; m-1) such that the number of mouses that have scared the Little Elephant is minimal possible. Print that number.

-----Input-----
First line contains single integer T - the number of test cases. Then T test cases follow. First line of each test case contain pair of integers n and m - the size of the board. Next n lines contain n strings, each of size m and consisted of digits 0 and 1.

-----Output-----
In T lines print T integer - the answers for the corresponding test.

-----Constraints-----
1 <= T <= 50
2 <= n, m <= 100

-----Example-----
Input:
2
3 9
001000001
111111010
100100100
7 9
010101110
110110111
010011111
100100000
000010100
011011000
000100101

Output:
9
10

-----Explanation-----
Example case 1: 
The optimized path is: (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (0, 8) -> (1, 8) -> (2, 8). The mouses that scared the Little Elephant are at the following cells: (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 7), (0, 2), (0, 8).

Example case 2: 
The optimized path is: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3) -> (4, 3) -> (4, 4) -> (5, 4) -> (5, 5) -> (6, 5) -> (6, 6) -> (6, 7) -> (6, 8). The 10 mouses that scared the Little Elephant are at the following cells: (0, 1), (1, 0), (1, 1), (2, 1), (3, 3), (4, 4), (5, 4), (5, 5), (6, 6), (6, 8).

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict
from itertools import product

def solve(mouse,n,m):
 
 # shadow matrix will contains the count of mice which affect (i,j) position
 # if there is a mice at position (i,j) then in shadow matrix it will affect         all four adjacent blocks 
 shadow=[[0 for i in range(m)]for j in range(n)]
 for i,j in product(list(range(n)),list(range(m))):
  if mouse[i][j]==1:
   if i>0:
    shadow[i-1][j]+=1
   if j>0:
    shadow[i][j-1]+=1
   if i<n-1:
    shadow[i+1][j]+=1
   if j<m-1:
    shadow[i][j+1]+=1
 
 # dp is a dictionary which contains a tuple of 3 values (i,j,0)=>we are         coming at destination (i,j) from left side
 # (i,j,1)=> we are coming at destination (i,j) from top 
 dp=defaultdict(int)
 
 # 
 dp[(0,0,0)]=dp[(0,0,1)]=shadow[0][0]-mouse[0][0]
 
 # fill only first row
 # in first row we can only reach at (0,j) from (0,j-1,0) as we can't come         from top.
 
 # so here we will assign count of mices which will affect current cell        (shadow[0][i]) + previous result i.e,(0,j-1,0) and 
 # if mouse is in the current cell than we have to subtract it bcoz we have         add it twice i.e, when we enter at this block 
 # and when we leave this block 
 for i in range(1,m):
  dp[(0,i,0)]=dp[(0,i,1)]=shadow[0][i]-mouse[0][i]+dp[(0,i-1,0)]
 
 # same goes for first column
 # we can only come at (i,0) from (i-1,0) i.e top
 for i in range(1,n):
  dp[(i,0,0)]=dp[(i,0,1)]=shadow[i][0]-mouse[i][0]+dp[(i-1,0,1)]
 
 
 # for rest of the blocks 
 # for a block (i,j) we have to add shadow[i][j] and subtract mouse[i][j]         from it for double counting
 # now for each block we have two choices, either take its previous block         with same direction or take previous block with different 
 # direction and subtract corner double counted mouse. We have to take min of         both to find optimal answer
 for i,j in product(list(range(1,n)),list(range(1,m))):
  a=shadow[i][j]-mouse[i][j]
  b=a
  a+=min(dp[(i,j-1,0)],dp[(i,j-1,1)]-mouse[i-1][j])
  b+=min(dp[(i-1,j,1)],dp[(i-1,j,0)]-mouse[i][j-1])
  dp[(i,j,0)]=a
  dp[(i,j,1)]=b
  
 # what if [0][0] and [n-1][m-1] have mice, so we have to add them as we         haven't counted them yet.
 
 return min(dp[(n-1,m-1,0)],dp[(n-1,m-1,1)])+mouse[0][0]+mouse[n-1][m-1]
    
for _ in range(int(input())):
 n,m=list(map(int,input().split( )))
 mouse=[]
 for i in range(n):
  x=input()
  mouse.append(list(map(int,x)))
 print(solve(mouse,n,m))
 
    
    
    
    
    
    
    
    
    


from collections import defaultdict
from itertools import product
def solve(mouse,n,m):
 shadow=[[0 for i in range(m)]for j in range(n)]
 for i,j in product(list(range(n)),list(range(m))):
  if mouse[i][j]==1:
   if i>0:
    shadow[i-1][j]+=1
   if j>0:
    shadow[i][j-1]+=1
   if i<n-1:
    shadow[i+1][j]+=1
   if j<m-1:
    shadow[i][j+1]+=1
 
 dp=defaultdict(int)
 dp[(0,0,0)]=dp[(0,0,1)]=shadow[0][0]-mouse[0][0]
 
 for i in range(1,m):
  dp[(0,i,0)]=dp[(0,i,1)]=shadow[0][i]-mouse[0][i]+dp[(0,i-1,0)]
 
 for i in range(1,n):
  dp[(i,0,0)]=dp[(i,0,1)]=shadow[i][0]-mouse[i][0]+dp[(i-1,0,1)]
 
 for i,j in product(list(range(1,n)),list(range(1,m))):
  a=shadow[i][j]-mouse[i][j]
  b=a
  a+=min(dp[(i,j-1,0)],dp[(i,j-1,1)]-mouse[i-1][j])
  b+=min(dp[(i-1,j,1)],dp[(i-1,j,0)]-mouse[i][j-1])
  dp[(i,j,0)]=a
  dp[(i,j,1)]=b
  
 
 return min(dp[(n-1,m-1,0)],dp[(n-1,m-1,1)])+mouse[0][0]+mouse[n-1][m-1]
    
for _ in range(int(input())):
 n,m=list(map(int,input().split( )))
 mouse=[]
 for i in range(n):
  x=input()
  mouse.append(list(map(int,x)))
 print(solve(mouse,n,m))