题目描述

有一个 $N \times N$ 的网格，位于从上往下第 $i$ 行和从左往右第 $j$ 列的单元格叫做 $(i,j)$。

网格由长度为 $N$ 的字符串 $S_1,S_2,\dots,S_N$ 描述。如果 $S_i$ 的第 $j$ 个字符是 .，$(i,j)$ 就是一个空单元格；如果是 #，$(i,j)$ 就是一个墙单元格。

最初，高桥君位于空单元格 $(N,C)$，并重复以下动作 $N-1$ 次：

• 如果他当前位于 $(r,c)$，则指定 $(r-1,c-1),(r-1,c),(r-1,c+1)$ 中的一个作为目的地。在此，他不能指定网格中不存在的单元格作为目的地。
• 如果目的地 $(a,b)$ 是一个墙单元格，则会出现以下情况：
  • 如果对于所有满足 $a < i \le N$ 的整数 $i$，即 $i\in[a+1,N]$，$(i,b)$ 当前是一个空单元格，那么他将摧毁位于 $(a,b)$ 的墙并移动到该处。也就是说，$(a,b)$ 变成空格，他移动到 $(a,b)$。
  • 否则，他将无法移动。在这种情况下，即使他没有进行 $N-1$ 次移动，也会立即结束移动。
• 如果目的地 $(a,b)$ 是一个空格，那么他会移动到 $(a,b)$。

输出长度为 $N$ 的字符串 $R$，满足以下条件：

• 如果他在移动过程中没有失败，可以到达 $(1,i)$，那么 $R$ 的第 $i$ 个字符是 1。
• 否则， $R$ 的第 $i$ 个字符为 0。

给你 $T$ 个测试用例，请逐一解决。

输入格式

输入内容由标准输入法提供，格式如下：

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

每个测试用例的格式如下：

$N$ $C\\$ $S_1\\$ $S_2\\$ $\vdots\\$ $S_N\\$

输出格式

输出 $T$ 行。

第 $i$ 行应包含第 $i$ 个测试用例的答案。

输入输出样例 #1

输入 #1

5
5 3
.###.
..#..
#.#.#
#...#
##..#
2 2
##
..
4 1
####
####
####
.###
3 3
...
...
...
10 3
##.##.##.#
.####..#..
...#.#..#.
.#.#.#.#..
...####...
#.#.##....
.##...#...
#.##.....#
#....###.#
.#..#.#...

输出 #1

10111
11
1000
111
0011010010

说明/提示

样例 $1$ 解释

此输入包含五个测试用例。

例如，对于第一个测试用例，他可以在如下运动中到达 $(1,3)$ 而不会失败：

• 最初，他位于 $(5,3)$。
• 他移动到空格 $(4,2)$。
• $(3,3)$ 是一个有墙的单元格，但是由于 $(4,3),(5,3)$ 目前都是空单元格，他摧毁了 $(3,3)$ 处的墙并移动到 $(3,3)$。
• $(2,3)$ 是一个有墙的单元格，但是由于 $(3,3),(4,3),(5,3)$ 目前都是空格，因此他摧毁了 $(2,3)$ 处的墙，并移动到 $(2,3)$ 处。
• $(1,3)$ 是一个有墙的单元格，但是由于 $(2,3),(3,3),(4,3),(5,3)$ 目前都是空格，因此他摧毁了 $(1,3)$ 处的墙，并移动到 $(1,3)$ 处。

他可以到达 $(1,1),(1,3),(1,4),(1,5)$ 而不会在移动过程中失败，因此打印 10111。

数据规模与约定

• $T,N,C$ 是整数
• $1 \le T \le 50000$
• $2 \le N \le 3000$
• $1 \le C \le N$
• $S_i$ 是长度为 $N$ 的字符串，由 . 和 # 组成
• $S_N$ 的第 $C$ 个字符是 .
• 对于每个输入，$N^2$ 的总和不超过 $9 \times 10^6$