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\ndef solve(mouse,n,m):\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=defaultdict(int)\n dp[(0,0,0)]=dp[(0,0,1)]=shadow[0][0]-mouse[0][0]\n \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 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 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 \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