有一个 N \times N 的网格。从上往下第 i 行、从左往右第 j 列的格子记为 (i,j)。网格由 N 个字符串 S_1, S_2, \dots, S_N 给出：S_i 的第 j 个字符为 `.` 表示 (i,j) 是空单元格，为 `#` 表示 (i,j) 是墙单元格。

一开始，小Z位于空单元格 (N, C)，并重复进行以下移动 N-1 次：

- 当前位于 (r, c) 时，从 (r-1, c-1), (r-1, c), (r-1, c+1) 中选择一个作为移动目的地。但不能指定网格中不存在的格子。

- 如果目的地 (a, b) 是墙单元格，则会发生以下情况：

  - 若当前所有满足 a < i \le N 的 (i, b) 均为空单元格，则摧毁 (a, b) 处的墙并移动过去。也就是说，(a, b) 变成空单元格，小Z移动到 (a, b)。

  - 否则移动失败。此时即使移动次数不足 N-1 次，也会立刻停止移动。

- 如果目的地 (a, b) 是空单元格，则直接移动过去。

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

- 若移动过程中没有失败并能到达 (1, i)，则 R 的第 i 个字符为 `1`；

- 否则 R 的第 i 个字符为 `0`。

给定 T 个测试用例，请分别求出每个用例的答案。

输入以如下格式从标准输入给出：

T

case_1

case_2

...

case_T

每个测试用例以如下格式给出：

N C

S_1

S_2

...

S_N

输出 T 行。

第 i 行输出第 i 个测试用例的答案字符串。

- 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。

样例1说明

第 1 次移动（行5 → 行4）

从 `(5,3)` 可以到 `(4,2)`、`(4,3)`、`(4,4)`，因为这三个格子都是 `.`。

第 2 次移动（行4 → 行3）

- 从 `(4,2)` 可到 `(3,2)`（`.`）和 `(3,3)`（`#`，但第3列下方 `(4,3)`、`(5,3)` 都是 `.`，所以可以摧毁并进入）。

- 从 `(4,3)` 可到 `(3,2)`、`(3,3)`、`(3,4)`（都是 `.` 或可摧毁的 `#`）。

- 从 `(4,4)` 可到 `(3,3)`、`(3,4)`（`(3,5)` 是 `#`，但第5列下方 `(4,5)`、`(5,5)` 都是 `#`，不能摧毁）。

所以第 3 行可达的列是：**2, 3, 4**。

第 3 次移动（行3 → 行2）

- 从 `(3,2)` 可到 `(2,1)`、`(2,2)`、`(2,3)`（`(2,3)` 是 `#`，但第3列下方已被清空，可以摧毁）。

- 从 `(3,3)` 可到 `(2,2)`、`(2,3)`、`(2,4)`。

- 从 `(3,4)` 可到 `(2,3)`、`(2,4)`、`(2,5)`。

所以第 2 行可达的列是：**1, 2, 3, 4, 5**。

第 4 次移动（行2 → 行1）

这是最后一步，需要到达第一行。检查每个可能的终点：

- **列1**：`(1,1)` 是 `.`，从 `(2,1)` 或 `(2,2)` 都可以直接进入 → **可达**。

- **列2**：`(1,2)` 是 `#`。要摧毁它，必须保证第2列在行2到行5的所有格子都是 `.`。但第2列最底部 `(5,2)` 是 `#`（见网格第5行第2列是 `#`），所以这堵墙无法被摧毁。因此 **不可达**。

- **列3**：`(1,3)` 是 `#`。第3列下方：`(2,3)` 原本是 `#`，但在之前的路径中已经被摧毁变成 `.`；`(3,3)` 也是 `#`，同样被摧毁；`(4,3)`、`(5,3)` 本来就是 `.`。所以第3列下方全是空地，可以摧毁 `(1,3)` → **可达**。

- **列4**：`(1,4)` 是 `#`。第4列下方：`(2,4)`、`(3,4)`、`(4,4)`、`(5,4)` 全是 `.`，可以摧毁 → **可达**。

- **列5**：`(1,5)` 是 `.`，从 `(2,5)` 或 `(2,4)` 可以进入 → **可达**。

最终第一行可达的列是：**1, 3, 4, 5**。  

所以输出字符串为：第1位 `1`，第2位 `0`，第3位 `1`，第4位 `1`，第5位 `1`，即 **`10111`**。