K. One More One
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary grid $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns.

Three cells form an angle if they can be written as $$$(i,j)$$$, $$$(i,y)$$$, and $$$(x,j)$$$, where $$$x \ne i$$$ and $$$y \ne j$$$, and all three cells contain $$$1$$$. The cell $$$(i,j)$$$ is the corner of the angle.

You must choose exactly one cell containing $$$0$$$ and change it to $$$1$$$.

Find the maximum possible number of angles after the change, and the number of cells whose change gives this maximum.

It is guaranteed that the grid contains at least one $$$0$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — the number of rows and columns.

Each of the next $$$n$$$ lines contains a binary string of length $$$m$$$ describing one row of the grid.

Each test case contains at least one $$$0$$$.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two integers: the maximum possible number of angles and the number of cells whose change gives this maximum.

Example
Input
5
2 2
10
01
2 2
11
10
3 3
110
100
000
2 3
111
000
1 4
1010
Output
1 2
4 1
4 1
2 3
0 2
Note

In the first test case, either zero creates one angle. In the second, changing the only zero makes each of the four cells the corner of an angle. In the fourth, any cell in the second row creates two angles. In the fifth, a one-row grid cannot contain an angle, so either zero is optimal.