B. Кис-кис-кис
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кошек привлекает «кис-кис-кис», но Эвирир, будучи достойным англоговорящим драконом, отзывается только на «pspspsp» с особыми условиями...

Дана строка $$$s = s_1s_2\ldots s_n$$$ длины $$$n$$$, состоящая из символов p, s и . (точка). Определите, существует ли перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, такая, что для каждого целого $$$i$$$ ($$$1 \le i \le n$$$):

  • Если $$$s_i$$$ равно p, то $$$[p_1, p_2, \ldots, p_i]$$$ образует перестановку (длины $$$i$$$);
  • Если $$$s_i$$$ равно s, то $$$[p_i, p_{i+1}, \ldots, p_{n}]$$$ образует перестановку (длины $$$n-i+1$$$);
  • Если $$$s_i$$$ равно ., то дополнительных ограничений нет.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 500$$$) — длина $$$s$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов p, s и ..

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных в первой строке выведите YES или NO. Выведите YES, если искомая перестановка существует, и NO в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
9
4
s.sp
6
pss..s
5
ppppp
2
sp
4
.sp.
8
psss....
1
.
8
pspspsps
20
....................
Выходные данные
YES
NO
YES
YES
NO
NO
YES
NO
YES
Примечание

Для первого набора входных данных одна подходящая перестановка такова: $$$p = [3, 4, 1, 2]$$$. Для неё выполняются все условия:

  • $$$s_1 =$$$ s : $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ образует перестановку.
  • $$$s_2 =$$$ . : Никаких дополнительных ограничений.
  • $$$s_3 =$$$ s : $$$[p_3, p_4] = [1, 2]$$$ образует перестановку.
  • $$$s_4 =$$$ p : $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ образует перестановку.

Для второго набора входных данных можно доказать, что не существует перестановки, удовлетворяющей всем ограничениям.

Для третьего набора входных данных одной перестановкой, удовлетворяющей условиям, является $$$p = [1, 2, 3, 4, 5]$$$.