Corners
Description
You are given a matrix consisting of $n$ rows and $m$ columns. Each cell of this matrix contains $0$ or $1$.
Let's call a square of size $2 \times 2$ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $1$ and replace all numbers in it with zeroes.
Find the maximum number of operations that you can do with the given matrix.
The first line contains one integer $t$ ($1 \leq t \leq 500$) — the number of test cases. Then follow the descriptions of each test case.
The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 500$) — the size of the matrix.
Each of the following $n$ lines contains a binary string of length $m$ — the description of the matrix.
It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $1000$.
For each test case output the maximum number of operations you can do with the given matrix.
Input
The first line contains one integer $t$ ($1 \leq t \leq 500$) — the number of test cases. Then follow the descriptions of each test case.
The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 500$) — the size of the matrix.
Each of the following $n$ lines contains a binary string of length $m$ — the description of the matrix.
It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $1000$.
Output
For each test case output the maximum number of operations you can do with the given matrix.
Samples
<div class="test-example-line test-example-line-even test-example-line-0">4</div><div class="test-example-line test-example-line-odd test-example-line-1">4 3</div><div class="test-example-line test-example-line-odd test-example-line-1">101</div><div class="test-example-line test-example-line-odd test-example-line-1">111</div><div class="test-example-line test-example-line-odd test-example-line-1">011</div><div class="test-example-line test-example-line-odd test-example-line-1">110</div><div class="test-example-line test-example-line-even test-example-line-2">3 4</div><div class="test-example-line test-example-line-even test-example-line-2">1110</div><div class="test-example-line test-example-line-even test-example-line-2">0111</div><div class="test-example-line test-example-line-even test-example-line-2">0111</div><div class="test-example-line test-example-line-odd test-example-line-3">2 2</div><div class="test-example-line test-example-line-odd test-example-line-3">00</div><div class="test-example-line test-example-line-odd test-example-line-3">00</div><div class="test-example-line test-example-line-even test-example-line-4">2 2</div><div class="test-example-line test-example-line-even test-example-line-4">11</div><div class="test-example-line test-example-line-even test-example-line-4">11</div><div class="test-example-line test-example-line-even test-example-line-4"></div>
8
9
0
2
Note
In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed):
- Matrix before any operation was performed:
1 0 1 1 1 1 0 1 1 1 1 0 - Matrix after $1$ operation was performed:
1 0 0 1 0 1 0 1 1 1 1 0 - Matrix after $2$ operations were performed:
1 0 0 1 0 0 0 1 1 1 1 0 - Matrix after $3$ operations were performed:
1 0 0 1 0 0 0 1 0 1 1 0 - Matrix after $4$ operations were performed:
1 0 0 0 0 0 0 1 0 1 1 0 - Matrix after $5$ operations were performed:
1 0 0 0 0 0 0 1 0 1 0 0 - Matrix after $6$ operations were performed:
1 0 0 0 0 0 0 0 0 1 0 0 - Matrix after $7$ operations were performed:
0 0 0 0 0 0 0 0 0 1 0 0 - Matrix after $8$ operations were performed:
0 0 0 0 0 0 0 0 0 0 0 0
In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones.
In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $2$ operations.