Mani 将 Hamid 锁定在 $$$1 \times n$$$ 网格中。最初,网格的某些单元格包含墙壁,其余单元格是空的,而哈米德位于空单元格中。
每天,以下事件按顺序发生:
- Mani 选择一个空单元格并在该单元格中建造一堵墙。请注意,他可以 不 在哈米德当前所在的牢房中建造一堵墙;
- Hamid 选择一个方向(左或右),然后
- 如果那个方向没有墙壁,他就会逃离网格;
- 否则,他会移动到该方向最近的墙壁并摧毁该墙壁。这一天之后,哈米德就位于被毁墙的位置。
以下是 $$$n=6$$$ 时可能的操作序列示例:
哈米德是 总是 知道墙壁在哪里。他想尽量减少逃离电网所需的天数,而玛尼则想最大化。
如果他们都表现最佳,你必须确定哈米德需要逃离网格的天数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x \leq n$$$) — 网格的大小和 Hamid 的初始位置。他最初位于从左到右第 $$$x$$$ 个牢房。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$ ($$$s_i=\texttt{"#"}$$$ 或 $$$\texttt{"."}$$$) — 网格的初始状态。如果 $$$s_i= \texttt{"#"}$$$,则网格的第 $$$i$$$ 个单元格包含一堵墙;如果 $$$s_i=\texttt{"."}$$$,则该单元格为空。
保证第$$$x$$$个单元格为空,并且网格中至少有两个空单元格。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 如果两者都表现最佳,哈米德需要逃离网格的天数。
示例
输入复制
43 1..#4 2....5 3##..#6 4#...#.
输出复制
1 1 3 3
注意
在第一个测试用例中,Mani 必须在单元格 $$$2$$$ 中建造一堵墙,以便哈米德可以在第一天从网格左侧逃脱。
在第二个测试用例中,如果Mani将墙放在Hamid的左侧,Hamid可以从右侧逃脱。如果墙在哈米德的右边,他就可以从左边逃跑。因此,答案是$$$1$$$。
在第三个测试用例中:
可以看出,在上图中,两位玩家的表现都是最佳的。
在第四个测试用例中,我们展示了语句中操作的示例。请注意,玩家们做到了 不 在此示例中表现最佳。