Problem Statement

There is an $N \times N$ grid. The cell at the $i$-th row from the top and $j$-th column from the left is called $(i,j)$. The grid is described by $N$ strings $S_1,S_2,\dots,S_N$. If the $j$-th character of $S_i$ is ., $(i,j)$ is an empty cell; if it is #, $(i,j)$ is a wall cell.

Initially, Takahashi-kun is at empty cell $(N,C)$, and repeats the following movement $N-1$ times:

• If he is currently at $(r,c)$, he specifies one of $(r-1,c-1),(r-1,c),(r-1,c+1)$ as the destination. Here, he cannot specify a cell that does not exist in the grid as the destination.
• If the destination $(a,b)$ is a wall cell, the following occurs:
• If $(i,b)$ is currently an empty cell for all integers satisfying $a < i \le N$, he destroys the wall at $(a,b)$ and moves there. That is, $(a,b)$ becomes an empty cell and he moves to $(a,b)$.
  • Otherwise, he fails to move. In this case, he immediately ends the repetition of movements, even if he has not made $N-1$ movements.
• If the destination $(a,b)$ is an empty cell, he moves to $(a,b)$.

Output a string $R$ of length $N$ satisfying the following conditions:

• If he can reach $(1,i)$ without failing during the movements, the $i$-th character of $R$ is 1.
• Otherwise, the $i$-th character of $R$ is 0.

You are given $T$ test cases; solve each of them.

Constraints

• $T,N,C$ are integers.
• $1 \le T \le 50000$
• $2 \le N \le 3000$
• $1 \le C \le N$
• $S_i$ is a string of length $N$ consisting of . and #.
• The $C$-th character of $S_N$ is ..
• For each input, the sum of $N^2$ does not exceed $9 \times 10^6$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N C
S_1
S_2
\vdots
S_N

Output

Print $T$ lines.

The $i$-th line should contain the answer for the $i$-th test case.