Вам дана доска размера \(2 \times n\) (\(2\) строки, \(n\) столбцов). В некоторых клетках доски находятся фигуры. Фигура представлена символом '*', а пустое место представлено символом '.'. Гарантируется, что на доске находится хотя бы одна фигура.
За один ход вы можете выбрать любую фигуру и сдвинуть ее в любую соседнюю (по стороне) клетку доски (если эта клетка находится на доске). Это значит, что если фигура находится в первом ряду, вы можете сдвинуть ее влево, вправо или вниз (но она не должна покидать пределы доски). То же самое с фигурой во второй строке — вы можете сдвинуть ее влево, вправо или вверх.
Если фигура попадает в клетку с другой фигурой, фигура в клетке назначения исчезает (то есть наша фигура ест ее).
Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы оставить ровно одну фигуру на доске.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное количество ходов, необходимое для того, чтобы оставить ровно одну фигуру на доске.