На уроке геометрии Искандеру было очень скучно, поэтому он решил разрисовать тетрадь Юры. Для этого он брал очередную строку и рисовал на ней горизонтальные линии. Где-то линии длинные, где-то короткие, а где-то страница осталась чистой.
Страница представлена строкой $$$s$$$, где символ '*' — чистый участок бумаги, а символ '#' — сантиметр нарисованной линии. Непрерывная последовательность символов '#' образует одну линию.
Юра решил стереть все линии и заставил Искандера ему помочь: они будут стирать одну из линий с двух концов одновременно.
Юра хочет выбрать линию так, чтобы вместе с Искандером стирать ее как можно дольше. Помогите ему определить это максимальное время. Если линии на странице нет, стирание длится $$$0$$$ секунд.
Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 2500$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10$$$) — длина строки $$$s$$$.
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$ из символов '#' и '*'.
Для каждого набора входных данных выведите одно число — максимальную длительность стирания среди всех линий.
57#*##*##8########8********8#*****##6*#####
14013
| Codeforces Round 1109 (Div. 3) |
|---|
| Закончено |
