B. Особые предпочтения в фильмах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Mihai планирует посмотреть фильм. Ему нравятся только фильмы-палиндромы, поэтому он хочет пропустить некоторые (возможно, ноль) сцен, чтобы оставшиеся части фильма образовали палиндром.

Вам дан список $$$s$$$ из $$$n$$$ непустых строк длины не более $$$3$$$, представляющих сцены из фильма Mihai.

Подпоследовательность $$$s$$$ называется классной, если она не пуста и конкатенация строк подпоследовательности по порядку является палиндромом.

Можете ли вы помочь Mihai проверить, есть ли хотя бы одна классная подпоследовательность $$$s$$$?

Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, строки «z», «aaa», «aba», «abccba» являются палиндромами, а строки «codeforces», «reality», «ab» таковыми не являются.

Последовательность $$$a$$$ называется непустой подпоследовательностью последовательности $$$b$$$, если $$$a$$$ получается из $$$b$$$ удалением нескольких (возможно, нуля, но не всех) элементов.

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество тестов. Далее следует описание тестовых случаев.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество сцен в фильме.

Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит единственную непустую строку $$$s_i$$$ длины не более $$$3$$$, состоящую из строчных латинских букв.

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

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

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

Пример
Входные данные
6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab
Выходные данные
YES
NO
NO
YES
YES
NO
Примечание

В первом наборе входных данных из $$$s$$$ можно выбрать классную подпоследовательность $$$[ab, cc, ba]$$$.