题目描述

Alice 将 Bob 困在一个 $1 \times n$ 的网格中。初始时，网格中的一些格子有墙，其余的格子为空，Bob 位于其中一个空格子中。

在每一天里，以下事件会按顺序发生：

1. Alice 选择一个空格子并在该格子中建一堵墙。注意，他不能在 Bob 当前所在的格子建墙；
2. Bob 选择一个方向（向左或向右），然后：
   • 如果在这个方向上没有任何墙，他将逃出网格；
   • 否则，他会移动到该方向上离他最近的墙，并将其摧毁。在这一天结束时，Bob 会停留在被摧毁的墙所在的位置。

以下是当 $n=6$ 时，一种可能的操作序列示例：

Bob 总是清楚墙壁的位置。Bob 希望最小化逃出网格所需的天数，而 Alice 希望最大化这个天数。

如果两人都采取最优策略，请你计算 Bob 逃出网格所需的天数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $x$（$2 \le n \le 2 \times 10^5$，$1 \le x \le n$）—— 分别表示网格的大小和 Bob 的初始位置。初始时，他位于从左到右数第 $x$ 个格子。
• 第二行包含一个长度为 $n$ 的字符串 $s$（$s_i$ 为 # 或 .）—— 表示网格的初始状态。如果 $s_i$ 是 #，表示第 $i$ 个格子有一堵墙；如果 $s_i$ 是 .，表示它是空的。

保证第 $x$ 个格子是空的，且网格中至少有两个空格子。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示在双方都采取最优策略的情况下，Bob 逃出网格所需的天数。

样例输入 1

4
3 1
..#
4 2
....
5 3
##..#
6 4
#...#.

样例输出 1

1
1
3
3

说明

样例解释

• 在第一个测试用例中，Alice 必须在第 $2$ 个格子建墙，因此 Bob 在第一天就可以从网格的左侧逃出。
• 在第二个测试用例中，如果 Alice 在 Bob 左侧建墙，Bob 可以从右侧逃出。如果墙建在 Bob 右侧，他可以从左侧逃出。因此答案为 $1$。
• 在第三个测试用例中：

可以证明上述图示中双方均采取了最优策略。

• 在第四个测试用例中，题目描述里展示了一种可能的操作示例。需要注意的是，在那个示例中，双方并没有采取最优策略。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $2 \le n \le 2 \times 10^5$，$1 \le x \le n$。
• 保证 $s$ 仅由 # 和 . 组成，$s_x$ 为 .，且 $s$ 中至少有两个 .。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。