时间限制： 每个测试 $1$ 秒
内存限制： 每个测试 $256$ MB

马尼把哈米德关在一个 $1 \times n$ 的网格里。初始时，网格的某些格子是墙，其余为空，哈米德位于某个空格子中。

每天，按顺序发生以下事件： 马尼选择一个空格子并在那里建一堵墙。注意他不能在哈米德当前所在的格子建墙； 哈米德选择一个方向（左或右），然后： 如果那个方向上没有墙，他就会逃出网格； 否则，他会向那个方向移动到最近的墙，并摧毁那堵墙。这一天结束后，哈米德位于被摧毁的墙的位置。

下面的例子展示了一个可能的过程（当 $n = 6$ 时）：

哈米德始终知道所有墙的位置。他希望最小化逃出网格所需的天数，而马尼则希望最大化这个天数。

如果双方都采取最优策略，你需要求出哈米德逃出网格所需的天数。

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$2 \le n \le 2 \cdot 10^5$，$1 \le x \le n$）—— 网格的大小和哈米德的初始位置。他从左往右数第 $x$ 个格子开始。

第二行包含一个长度为 $n$ 的字符串 $s$（$s_i =$ # 或 .）—— 网格的初始状态。如果 $s_i =$ #，则表示第 $i$ 个格子是墙；如果 $s_i =$ .，则表示空格子。

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

输出
对每个测试用例，输出一个整数 —— 若双方均采取最优策略，哈米德逃出网格所需的天数。

样例输入

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

样例输出

1
1
3
3

提示
在第一个测试用例中，马尼必须在第 $2$ 个格子建墙，因此哈米德可以在第一天从网格左侧逃出。

在第二个测试用例中，如果马尼在哈米德左侧建墙，哈米德可以从右侧逃出；如果墙建在右侧，哈米德可以从左侧逃出。因此答案为 $1$。

在第三个测试用例中，可以说明图中的过程双方都采取了最优策略。

在第四个测试用例中，题面给出了一种可能的行动示例，但注意该示例中双方并未采取最优策略。