C. Специальная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

AksLolCoding играет в игру со строкой $$$s$$$ длиной $$$n$$$. Изначально $$$s$$$ содержит только строчные латинские буквы.

В один ход AksLolCoding может выбрать любую пару целых чисел $$$(i,j)$$$ такие, что:

  • $$$1 \leq i \lt j \leq n$$$;
  • $$$s_i = s_j \neq *$$$; и
  • $$$s_k = *$$$ для всех $$$i \lt k \lt j$$$.
Если такой пары $$$i,j$$$ не существует, то игра заканчивается. В противном случае AksLolCoding присваивает $$$s_i:=*$$$ и $$$s_j:=*$$$.

Как только игра заканчивается, AksLolCoding выигрывает, если и только если каждый символ в $$$s$$$ равен $$$*$$$. Определите, возможно ли AksLolCoding выиграть.

Примечание: $$$*$$$ представляет собой ASCII символ 42.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 100$$$), количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$), длину строки.

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

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

Выведите ответ для каждого набора входных данных на отдельной строке. Если AksLolCoding может выиграть, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек). Регистр не имеет значения.

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

Пример
Входные данные
6
1
a
6
llmllm
6
uwuuwu
6
byebye
6
oooioi
12
siixxsevvenn
Выходные данные
NO
YES
YES
NO
NO
YES
Примечание

В первом наборе входных данных можно показать, что AksLolCoding не может выиграть.

Во втором наборе входных данных AksLolCoding может выиграть, сделав следующие ходы: llmllm $$$\rightarrow$$$ llm**m $$$\rightarrow$$$ **m**m $$$\rightarrow$$$ ******

В третьем наборе входных данных AksLolCoding может выиграть, сделав следующие ходы: uwuuwu $$$\rightarrow$$$ uw**wu $$$\rightarrow$$$ u****u $$$\rightarrow$$$ ******