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).

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from collections import defaultdict\nfrom itertools import product\n\ndef solve(mouse,n,m):\n \n # shadow matrix will contains the count of mice which affect (i,j) position\n # if there is a mice at position (i,j) then in shadow matrix it will affect \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0all four adjacent blocks \n shadow=[[0 for i in range(m)]for j in range(n)]\n for i,j in product(list(range(n)),list(range(m))):\n  if mouse[i][j]==1:\n   if i>0:\n    shadow[i-1][j]+=1\n   if j>0:\n    shadow[i][j-1]+=1\n   if i<n-1:\n    shadow[i+1][j]+=1\n   if j<m-1:\n    shadow[i][j+1]+=1\n \n # dp is a dictionary which contains a tuple of 3 values (i,j,0)=>we are \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0coming at destination (i,j) from left side\n # (i,j,1)=> we are coming at destination (i,j) from top \n dp=defaultdict(int)\n \n # \n dp[(0,0,0)]=dp[(0,0,1)]=shadow[0][0]-mouse[0][0]\n \n # fill only first row\n # in first row we can only reach at (0,j) from (0,j-1,0) as we can't come \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0from top.\n \n # so here we will assign count of mices which will affect current cell\xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0(shadow[0][i]) + previous result i.e,(0,j-1,0) and \n # if mouse is in the current cell than we have to subtract it bcoz we have \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0add it twice i.e, when we enter at this block \n # and when we leave this block \n for i in range(1,m):\n  dp[(0,i,0)]=dp[(0,i,1)]=shadow[0][i]-mouse[0][i]+dp[(0,i-1,0)]\n \n # same goes for first column\n # we can only come at (i,0) from (i-1,0) i.e top\n for i in range(1,n):\n  dp[(i,0,0)]=dp[(i,0,1)]=shadow[i][0]-mouse[i][0]+dp[(i-1,0,1)]\n \n \n # for rest of the blocks \n # for a block (i,j) we have to add shadow[i][j] and subtract mouse[i][j] \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0from it for double counting\n # now for each block we have two choices, either take its previous block \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0with same direction or take previous block with different \n # direction and subtract corner double counted mouse. We have to take min of \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0both to find optimal answer\n for i,j in product(list(range(1,n)),list(range(1,m))):\n  a=shadow[i][j]-mouse[i][j]\n  b=a\n  a+=min(dp[(i,j-1,0)],dp[(i,j-1,1)]-mouse[i-1][j])\n  b+=min(dp[(i-1,j,1)],dp[(i-1,j,0)]-mouse[i][j-1])\n  dp[(i,j,0)]=a\n  dp[(i,j,1)]=b\n  \n # what if [0][0] and [n-1][m-1] have mice, so we have to add them as we \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0haven't counted them yet.\n \n return min(dp[(n-1,m-1,0)],dp[(n-1,m-1,1)])+mouse[0][0]+mouse[n-1][m-1]\n    \nfor _ in range(int(input())):\n n,m=list(map(int,input().split( )))\n mouse=[]\n for i in range(n):\n  x=input()\n  mouse.append(list(map(int,x)))\n print(solve(mouse,n,m))\n \n    \n    \n    \n    \n    \n    \n    \n    \n    \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 24289