B. Выше облаков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита. Определите, существуют ли три непустые строки $$$a$$$, $$$b$$$ и $$$c$$$ такие, что:

  • $$$a + b + c = s$$$, то есть конкатенация$$$^{\text{∗}}$$$ строк $$$a$$$, $$$b$$$ и $$$c$$$ равна $$$s$$$.
  • Строка $$$b$$$ является подстрокой$$$^{\text{†}}$$$ строки $$$a + c$$$, то есть конкатенации строк $$$a$$$ и $$$c$$$.

$$$^{\text{∗}}$$$Конкатенацией строк $$$a$$$ и $$$b$$$ называется строка $$$a + b = a_1a_2 \ldots a_pb_1b_2 \ldots b_q$$$, где $$$p$$$ и $$$q$$$ длины строк $$$a$$$ и $$$b$$$ соответственно. Например, конкатенация строк «code» и «forces» равна «codeforces».

$$$^{\text{†}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов с начала и нескольких (возможно, ни одного или всех) символов с конца.

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

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

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — длина строки $$$s$$$.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите «Yes», если существует три непустые строки $$$a$$$, $$$b$$$ и $$$c$$$, удовлетворяющие условиям, и «No» иначе.

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

Пример
Входные данные
12
3
aaa
3
aba
3
aab
4
abca
4
abba
4
aabb
5
abaca
5
abcda
5
abcba
6
abcbbf
6
abcdaa
3
abb
Выходные данные
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Примечание

В первом наборе входных данных существуют единственные непустые строки $$$a$$$, $$$b$$$ и $$$c$$$ такие, что $$$a + b + c = s$$$. Это строки $$$a =$$$ «a», $$$b =$$$ «a» и $$$c =$$$ «a». Конкатенация строк $$$a$$$ и $$$c$$$ равна $$$a + c = $$$ «aa». Строка $$$b$$$ является подстрокой этой строки.

В шестом наборе входных данных можно выбрать $$$a = $$$ «a», $$$b = $$$ «ab» и $$$c = $$$ «b». Конкатенация строк $$$a$$$ и $$$c$$$ равна $$$a + c = $$$ «ab». Строка $$$b$$$ является подстрокой этой строки.

В седьмом наборе входных данных можно выбрать $$$a = $$$ «ab», $$$b = $$$ «a» и $$$c = $$$ «ca». Конкатенация строк $$$a$$$ и $$$c$$$ равна $$$a + c = $$$ «abca». Строка $$$b$$$ является подстрокой этой строки.