lemouse_5127
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).
#! /usr/bin/python

MAX_M = 100000

def xdiff(i, j, matrix, isYflow):
	""" coming to i,j position in the matrix from x direction. 
	isYflow states the direction of second last move considering this as last,
	0 represents from left, 1 from top and -1 for the case when both are possible.
	Returns the additional affected mice because of this x shift"""

	psum = get(i, j+1, matrix) + get(i+1, j, matrix)
	return psum if isYflow else psum + get(i-1, j, matrix)

def ydiff(i, j, matrix, isYflow):
	""" Read xdiff """

	psum = get(i+1, j, matrix) + get(i, j+1, matrix)
	return psum + get(i, j-1, matrix) if isYflow == 1 else psum

def get(i, j, matrix):
	""" returns matrix[i][j]. For the cases where i, j is not in matrix	returns 0. """

	n, m = len(matrix), len(matrix[0])
	if i < 0 or i >= n or j <  0 or j >= m:
		return 0
	else:
		return matrix[i][j]

def get_affected(i, j, matrix):
	""" Returns number of the affected mice for a given point """

	return (get(i+1, j, matrix) + get(i, j-1, matrix) + get(i, j+1, matrix) + get(i-1, j, matrix) + get(i, j, matrix))

l = int(raw_input()) # number of test cases
for x in xrange(0, l):
	input = raw_input().split(' ')
	n, m = int(input[0]), int(input[1])
	matrix = []  # matrix for each test case
	for y in xrange(0, n):
		matrix.append([int(c) for c in raw_input()])
	matrix_soln = []	# matrix_soln[i][j] = (least number of mice touched from 0,0 to i-1,j-1 in matrix, 0 or 1 based on last move from x or y position)
	# dynamic approach
	for i in xrange(0, n+1):
		current_row_soln = []
		for j in xrange(0, m+1):
			if i == 0: # initialization, for first column assume that the last move was from x direction i.e. coming from out of the box hence a 0
				current_row_soln.append((MAX_M, 0))
			elif j == 0: # coming from out of box from y direction hence a 1
				current_row_soln.append((MAX_M, 1))
			elif i == 1 and j == 1:
				current_row_soln.append((get_affected(i-1, j-1, matrix), 0))
			else:
				from_up = matrix_soln[i-1][j][0] + ydiff(i-1,j-1,matrix, matrix_soln[i-1][j][1])
				from_left = current_row_soln[j-1][0] + xdiff(i-1,j-1,matrix, current_row_soln[j-1][1])
				if from_up < from_left:
					soln = (from_up, 1)
				elif from_up > from_left:
					soln = (from_left, 0)
				else:
					soln = (from_up, -1)
				current_row_soln.append(soln)
		matrix_soln.append(current_row_soln)
#	for sol in matrix_soln:
#		print sol
	print matrix_soln[n][m][0]