Мани запер Хамида в таблице размером $$$1 \times n$$$. Изначально некоторые ячейки таблицы содержат стены, а остальные — пустые, и Хамид находится в пустой ячейке.
Каждый день по порядку происходят следующие события:
- Мани выбирает пустую ячейку и строит стену в этой ячейке. Обратите внимание, что он не может построить стену в ячейке, в которой сейчас находится Хамид;
- Хамид выбирает направление (влево или вправо), затем
- Если в этом направлении до конца таблицы нет стен, он сбежит из таблицы;
- В противном случае он переместится к ближайшей стене в этом направлении и разрушит эту стену. Хамид окажется на месте разрушенной стены после этого дня.
Вот пример возможной последовательности действий, когда $$$n=6$$$:
Хамид в любой момент времени знает, где расположены стены. Он хочет минимизировать количество дней, необходимых ему для побега из таблицы, в то время как Мани хочет максимизировать это количество.
Вам нужно определить количество дней, необходимых Хамиду для побега из таблицы, если они оба действуют оптимально.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x \leq n$$$) — размер таблицы и начальная позиция Хамида. Изначально он находится в $$$x$$$-й слева ячейке.
Вторая строка содержит строку $$$s$$$ длиной $$$n$$$ ($$$s_i=\texttt{"#"}$$$ или $$$\texttt{"."}$$$) — начальное состояние таблицы. $$$i$$$-я ячейка таблицы содержит стену, если $$$s_i= \texttt{"#"}$$$, и она пустая, если $$$s_i=\texttt{"."}$$$.
Гарантируется, что $$$x$$$-я ячейка пустая, и в таблице есть как минимум две пустые ячейки.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество дней, необходимых Хамиду для побега из таблицы, если они оба действуют оптимально.
43 1..#4 2....5 3##..#6 4#...#.
1 1 3 3
В первом наборе входных данных Мани должен построить стену в ячейке $$$2$$$, поэтому Хамид может сбежать с левой стороны таблицы в первый день.
Во втором наборе входных данных, если Мани поставит стену слева от Хамида, Хамид сможет сбежать справа. А если стена будет справа от Хамида, он сможет сбежать слева. Таким образом, ответ равен $$$1$$$.
В третьем наборе входных данных:
Можно показать, что оба игрока действовали оптимально на приведенной иллюстрации.
В четвертом наборе входных данных мы показали пример действий в условии. Обратите внимание, что игроки не действовали оптимально в этом примере.
