You are given a binary grid$^{\text{∗}}$ $G$ of dimensions $n \times m$.

Let us define a rectangle as a tuple $(u,d,l,r)$ that satisfies the following conditions:

• $1 \le \boldsymbol{u \lt d} \le n$;
• $1 \le \boldsymbol{l \lt r} \le m$;
• Cells $(u,l)$, $(u,r)$, $(d,l)$, $(d,r)$ all contain a $1$.

Then, the area of a rectangle $(u,d,l,r)$ is defined as $(d-u+1) \cdot (r-l+1)$.

For example, consider the following binary grid given below.

$$\begin{matrix} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix}$$

Here, you may see two rectangles $(1,2,1,3)$ and $(1,3,3,5)$$^{\text{†}}$, each of which has area $6$ and $9$, respectively.

For each cell $(i,j)$, find the minimum area of any rectangle $(u,d,l,r)$ such that $u \le i \le d$ and $l \le j \le r$.

$^{\text{∗}}$A binary grid is a grid where each cell contains $0$ or $1$. The cell on the $j$-th column of the $i$-th row is denoted as cell $(i,j)$.$^{\text{†}}$Note that these are the only rectangles in the grid; for example, $(1,1,1,5)$ is not a rectangle as it does not satisfy $u \lt d$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n,m$, $n\cdot m \le 250\,000$).

Each of the $n$ following lines contains a string of length $m$ denoting the $i$-th row of $G$ ($G_{i,j} \in \{0,1\}$).

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $250\,000$.

Output

For each test case, output a grid of $n$ rows and $m$ columns. On the $j$-th column of the $i$-th row, you should output:

• If there exists a rectangle $(u,d,l,r)$ such that $u \le i \le d$ and $l \le j \le r$, output the minimum area of any such rectangle;
• Otherwise, output $0$ instead.

Note

The first test case is explained in the statement.

For the third test case, there are six rectangles that cover at least one cell with minimum area:

• $(1,3,1,2)$, which has area $6$;
• $(1,2,1,3)$, which has area $6$;
• $(3,4,2,3)$, which has area $4$;
• $(2,3,3,4)$, which has area $4$;
• $(3,5,4,5)$, which has area $6$;
• $(4,5,3,5)$, which has area $6$.