Mihai plans to watch a movie. He only likes palindromic movies, so he wants to skip some (possibly zero) scenes to make the remaining parts of the movie palindromic.

You are given a list $s$ of $n$ non-empty strings of length at most $3$, representing the scenes of Mihai's movie.

A subsequence of $s$ is called awesome if it is non-empty and the concatenation of the strings in the subsequence, in order, is a palindrome.

Can you help Mihai check if there is at least one awesome subsequence of $s$?

A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

A sequence $a$ is a non-empty subsequence of a non-empty sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly zero, but not all) elements.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of scenes in the movie.

Then follows $n$ lines, the $i$-th of which containing a single non-empty string $s_i$ of length at most $3$, consisting of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print "YES" if there is an awesome subsequence of $s$, or "NO" otherwise (case insensitive).


-----Examples-----

Input
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
Output
YES
NO
NO
YES
YES
NO


-----Note-----

In the first test case, an awesome subsequence of $s$ is $[ab, cc, ba]$

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: String algorithms

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

def solve() -> str:
	n = I()
	s = [S() for _ in range(n)]
	st = set()
	st2 = set()
	if any((x[0] == x[-1] for x in s)):
		return 'YES'
	else:
		for x in s:
			if len(x) == 2 and x[::-1] in st:
				return 'YES'
			if len(x) == 3 and (x[::-1][:2] in st2 or x[::-1] in st2):
				return 'YES'
			st.add(x[:2])
			st2.add(x)
		return 'NO'
for _ in range(I()):
	print(solve())


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	s = set()
	e = set()
	ans = False
	for i in range(n):
		x = inp().strip()
		y = x[::-1]
		if x == y:
			ans = True
		elif y in s or y in e:
			ans = True
		elif len(y) > 1 and y[:-1] in s:
			ans = True
		s.add(x)
		if len(x) > 1:
			e.add(x[:-1])
	print(['NO', 'YES'][ans])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	scenes = [input().strip() for i in range(n)]
	seen_twos = set()
	seen_threes = set()
	seen_prefixes = set()
	can_make_palindrome = 'NO'
	for x in scenes:
		reverse = x[::-1]
		if x == reverse:
			can_make_palindrome = 'YES'
			break
		if len(x) == 2:
			if reverse in seen_twos or reverse in seen_prefixes:
				can_make_palindrome = 'YES'
				break
			seen_twos.add(x)
		elif len(x) == 3:
			if reverse in seen_threes or reverse[:-1] in seen_twos:
				can_make_palindrome = 'YES'
				break
			seen_threes.add(x)
			seen_prefixes.add(x[:-1])
	print(can_make_palindrome)


def solve():
	n = int(input())
	s = set()
	s2 = set()
	flg = 0
	for i in range(n):
		x = input()
		if flg == 1:
			continue
		n = len(x)
		xr = x[::-1]
		if x == xr or xr in s or n == 1:
			flg = 1
		if n == 2:
			if xr in s2:
				flg = 1
		if n == 3:
			if xr[:2] in s:
				flg = 1
			s2.add(x[:2])
		s.add(x)
	if flg == 0:
		print('NO')
	else:
		print('YES')
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [input() for i in range(n)]
	vis = set()
	al = set()
	ans = False
	for i in arr:
		al.add(i)
		if i[::-1] in al:
			ans = True
			break
		if len(i) == 3:
			if i[:0:-1] in al:
				ans = True
				break
			vis.add(i[1::-1])
		elif i in vis:
			ans = True
			break
	print('YES' if ans else 'NO')


for _ in range(int(input())):
	n = int(input())
	words = []
	yes = False
	for _ in range(n):
		word = input()
		words.append(word)
	d = set()
	substrings = set()
	for word in words:
		r = word[::-1]
		if r == word:
			print('YES')
			yes = True
			break
		if r in d or r in substrings:
			print('YES')
			yes = True
			break
		if len(word) == 3:
			if r[0:2] in d:
				print('YES')
				yes = True
				break
			substrings.add(word[0:2])
		d.add(word)
	if not yes:
		print('NO')


def solve():
	l = list()
	s = set()
	n = int(input())
	for _ in range(n):
		l.append(input().strip())
	for _ in range(n):
		tmp = l[_]
		le = len(tmp)
		if le == 1 or tmp == tmp[::-1]:
			print('YES')
			return
		if le == 2:
			if tmp[::-1] in s:
				print('YES')
				return
		elif le == 3:
			if tmp[::-1] in s or tmp[-1:-3:-1] in s:
				print('YES')
				return
		s.add(tmp)
	s = set()
	for _ in range(n - 1, -1, -1):
		tmp = l[_]
		le = len(tmp)
		if le == 3:
			if tmp[-2:-4:-1] in s:
				print('YES')
				return
		s.add(tmp)
	print('NO')
_t = int(input())
for _c in range(_t):
	solve()


for _ in range(int(input())):
	n = int(input())
	ans = 'NO'
	set1 = set()
	set2 = set()
	for i in range(n):
		s = input()
		ss = s[::-1]
		if s == ss or s in set2 or s in set1 or (s[1:] in set1):
			ans = 'YES'
		set1.add(ss)
		if len(ss) == 3:
			set2.add(ss[1:])
	print(ans)


def solve():
	n = int(input())
	v = [input().strip() for _ in range(n)]
	p23 = set()
	p32 = set()
	p22 = set()
	p33 = set()
	for e in v:
		if e == e[::-1]:
			print('YES')
			return
		if len(e) == 2:
			if e[::-1] in p22:
				print('YES')
				return
			if e[::-1] in p32:
				print('YES')
				return
			p22.add(e)
			p23.add(e)
		if len(e) == 3:
			if e[::-1] in p33 or e[::-1][:2] in p23:
				print('YES')
				return
			p33.add(e)
			p32.add(e[:2])
	print('NO')
	return
_t = 1
_t = int(input())
for _ in range(_t):
	solve()


def inp(n):
	(a, b, c) = (set(), set(), set())
	ans = False
	for i in range(n):
		s = input()
		if not ans:
			if len(s) == 1:
				ans = True
			elif len(s) == 2:
				b.add(s)
				k = s[::-1]
				if k in b:
					ans = True
				for i in 'abcdefghijklmnopqrstuvwxyz':
					if k + i in c:
						ans = True
			else:
				c.add(s)
				k = s[::-1]
				if k in c:
					ans = True
				if s[2] + s[1] in b:
					ans = True
	return ans
for _ in range(int(input())):
	n = int(input())
	ans = inp(n)
	if ans:
		print('YES')
	else:
		print('NO')


def solve(N, S):
	seen = {}
	seen_th = {}
	for word in S:
		if word == word[::-1] or word[::-1] in seen:
			return 'YES'
		if len(word) == 3 and word[1:][::-1] in seen:
			return 'YES'
		if len(word) == 2 and word[::-1] in seen_th:
			return 'YES'
		if len(word) == 3:
			seen_th[word[:2]] = 1
		seen[word] = 1
	return 'NO'
for _ in range(int(input())):
	print(solve((N := int(input())), [input() for _ in range(N)]))


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
for _ in range(int(input())):
	n = int(input())
	ans = 'NO'
	set1 = set()
	set2 = set()
	for i in range(n):
		s = input()
		ss = s[::-1]
		if s == ss or s in set2 or s in set1 or (s[1:] in set1):
			ans = 'YES'
		set1.add(ss)
		if len(ss) == 3:
			set2.add(ss[1:])
	print(ans)


import sys
from collections import Counter
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

def read_str():
	return input().strip()

def solve(words):
	s = set(words)
	for w in s:
		if len(w) == 1 or w == w[::-1] or w[::-1] in s:
			return 'YES'
	aux_3 = Counter()
	aux_2 = Counter()
	for w in words:
		if len(w) == 3:
			aux_3[w[1:][::-1]] += 1
		if len(w) == 2:
			aux_2[w[::-1]] += 1
	for w in words:
		if len(w) == 2:
			aux_2[w[::-1]] -= 1
			if w in aux_3 and aux_3[w] > 0:
				return 'YES'
		if len(w) == 3:
			aux_3[w[1:][::-1]] -= 1
			aux_w = w[:-1]
			if aux_w in aux_2 and aux_2[aux_w] > 0:
				return 'YES'
	return 'NO'
for _ in range(inp()):
	words = []
	for _ in range(inp()):
		words.append(read_str())
	print(solve(words))


for iii in range(int(input())):
	n = int(input())
	q = []
	for i in range(n):
		q.append(input())
	q1 = {}
	q2 = {}
	x = False
	for s in q:
		if s == s[::-1]:
			x = True
		elif s in q1 or s in q2:
			x = True
		elif len(s) == 3:
			q3 = s[1:]
			q4 = s[:2]
			if q3 in q1:
				x = True
			else:
				q1[s[::-1]] = 0
				q2[q4[::-1]] = 0
		else:
			q1[s[::-1]] = 0
			q2[s[::-1]] = 0
		if x:
			break
	if x:
		print('YES')
	else:
		print('NO')


from audioop import reverse

def isPalindrome(s):
	if s[0] == s[-1]:
		return True
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	flag = False
	numbers = []
	ans = 0
	two_letters = set()
	three_letters = set()
	for i in range(n):
		s = input()
		if ans:
			continue
		if isPalindrome(s):
			ans = 1
			continue
		reverseS = s[::-1]
		if len(s) == 2:
			if reverseS in two_letters:
				ans = 1
				continue
			if reverseS in three_letters:
				ans = 1
				continue
			two_letters.add(s)
		elif len(s) == 3:
			if reverseS in three_letters:
				ans = 1
				continue
			if reverseS[:2] in two_letters:
				ans = 1
				continue
			three_letters.add(s[:2])
			three_letters.add(s)
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	k = int(input())
	a = set()
	arr = []
	flag = False
	couples = set()
	for i in range(k):
		s = input()
		arr.append(s)
	for s in arr:
		if len(s) == 1:
			flag = True
			break
		elif len(s) == 2:
			if s[::-1] == s or s in a:
				flag = True
				break
			else:
				a.add(s[::-1])
				couples.add(s[::-1])
		elif s[::-1] == s or (s[1] + s[2] in a and s[1] + s[2] in couples) or s in a:
			flag = True
			break
		else:
			a.add(s[1] + s[0])
			a.add(s[::-1])
	if flag:
		print('YES')
	else:
		print('NO')


def can_form(scenes):
	for scene in scenes:
		if len(scene) == 1:
			return True
		elif scene[0] == scene[-1]:
			return True
	mem2 = {}
	mem3 = {}
	for scene in scenes:
		if len(scene) == 2:
			if scene[::-1] in mem2:
				return True
			mem2[scene] = ''
		if len(scene) == 3:
			if scene[1:][::-1] in mem2 and (mem2[scene[1:][::-1]] == scene[0] or mem2[scene[1:][::-1]] == ''):
				return True
			if scene[::-1] in mem3:
				return True
			mem2[scene[:-1]] = scene[-1]
			mem3[scene] = ''
	return False
T = int(input())
for t in range(T):
	n = int(input())
	scenes = []
	for k in range(n):
		scenes.append(input())
	if can_form(scenes):
		print('YES')
	else:
		print('NO')


def is_palindrom(w):
	if len(w) == 1:
		return True
	if len(w) == 2:
		return w[0] == w[1]
	if w[0] != w[-1]:
		return False
	return is_palindrom(w[1:-1])

def has_sub_palindrom(words):
	for w in words:
		if is_palindrom(w):
			return True
	set_of_words_so_far = set()
	pair_of_threes = set()
	for w in words:
		if is_palindrom(w):
			return True
		if w[::-1] in set_of_words_so_far:
			return True
		if len(w) == 3:
			if w[2] + w[1] in set_of_words_so_far:
				return True
			pair_of_threes.add(w[0] + w[1])
		if len(w) == 2:
			if w[::-1] in pair_of_threes:
				return True
		set_of_words_so_far.add(w)
	return False
T = int(input())
for _ in range(T):
	n = int(input())
	words = [input() for _ in range(n)]
	if has_sub_palindrom(words):
		print('YES')
	else:
		print('NO')


ans = []
for _ in range(int(input())):
	n = int(input())
	x = dict()
	q = False
	for i in range(n):
		s = input()
		x[s] = 1
		if len(s) == 1:
			q = True
		if s not in x:
			x[s] = 1
		s1 = s[::-1]
		if s1 in x:
			q = True
		if len(s) == 3:
			s1 = s[1:]
			s1 = s1[::-1]
			if s1 in x and x[s1] == 1:
				q = True
			s1 = s[:2]
			x[s1] = 0
	if q == True:
		ans.append('YES')
	else:
		ans.append('NO')
print('\n'.join([str(i) for i in ans]))


def evaluate(a):
	vals = {}
	for x in a:
		if len(x) == 1:
			return True
		elif len(x) == 2 and x[0] == x[1]:
			return True
		elif len(x) == 3 and x[0] == x[2]:
			return True
		elif len(x) == 2:
			if x in vals:
				return True
			vals[x[1] + x[0]] = 2
		elif len(x) == 3:
			if x in vals:
				return True
			if x[1] + x[2] in vals and vals[x[1] + x[2]] == 2:
				return True
			vals[x[2] + x[1] + x[0]] = 3
			vals[x[1] + x[0]] = 3
	return False
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for x in range(n):
		v = input()
		a.append(v)
	val = evaluate(a)
	if val:
		print('YES')
	else:
		print('NO')


T = int(input())

def solve():
	set_strings = set()
	n = int(input())
	answer = 'NO'
	for i in range(n):
		s = input()
		set_strings.add((s, len(s)))
		if len(s) == 3:
			set_strings.add((s[:2], len(s)))
		if (s[::-1], len(s)) in set_strings:
			answer = 'YES'
		if len(s) == 3 and (s[::-1][:2], 2) in set_strings:
			answer = 'YES'
		if len(s) == 2 and (s[::-1][:2], 3) in set_strings:
			answer = 'YES'
	return answer
for t in range(T):
	print(solve())


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = []
	c = 0
	for i in range(n):
		s = input()
		if len(s) == 1:
			c = 1
		elif s[0] == s[-1]:
			c = 1
		a.append(s)
	if c == 1:
		print('YES')
		continue
	d = {}
	for i in a:
		f = i[:2]
		b = i[len(i) - 2:len(i)][::-1]
		if b in d:
			if len(i) == 2:
				print('YES')
				break
			elif i[0] in d[b] or '#' in d[b]:
				print('YES')
				break
		m = '#'
		if len(i) == 3:
			m = i[-1]
		if f in d:
			d[f].add(m)
		else:
			d[f] = set([m])
	else:
		print('NO')


import sys
import re
import math
from math import log2 as lg
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	m = int(input())
	ok = False
	d = {}
	d3 = {}
	for j in range(m):
		curr = input()
		if ok:
			continue
		if len(curr) == 1:
			ok = True
		elif len(curr) == 2 and curr[0] == curr[1]:
			ok = True
		elif len(curr) == 3 and curr[0] == curr[1] and (curr[1] == curr[2]):
			ok = True
		elif curr == curr[::-1]:
			ok = True
		elif len(curr) == 2:
			temp = curr[::-1]
			if temp in d or temp in d3:
				ok = True
			d[curr] = 0
		elif len(curr) == 3:
			lasttwo = curr[2] + curr[1]
			if lasttwo in d:
				ok = True
			elif lasttwo in d3 and curr[0] in d3[lasttwo]:
				ok = True
			firsttwo = curr[0] + curr[1]
			if firsttwo in d3:
				d3[firsttwo][curr[2]] = 0
			else:
				d3[firsttwo] = {}
				d3[firsttwo][curr[2]] = 0
	if ok:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = []
	a = set()
	b = set()
	t = 0
	for i in range(n):
		s = input()
		arr.append(s)
	for s in arr:
		if len(s) == 1:
			t = 1
			break
		elif len(s) == 2:
			if s[::-1] == s or s in a:
				t = 1
				break
			else:
				a.add(s[::-1])
				b.add(s[::-1])
		elif s[::-1] == s or (s[1] + s[2] in a and s[1] + s[2] in b) or s in a:
			t = 1
			break
		else:
			a.add(s[1] + s[0])
			a.add(s[::-1])
	if t == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	z = []
	for i in range(n):
		z.append(str(input()))
	f = False
	for s in z:
		if s == s[::-1]:
			print('YES')
			f = True
			break
	if f:
		continue
	seen = set()
	for s in z:
		if s[::-1] in seen:
			print('YES')
			f = True
			break
		seen.add(s)
	if f:
		continue
	seen = set()
	for s in z:
		if len(s) == 2:
			seen.add(s)
		else:
			trail_2 = s[1:]
			trail_2 = trail_2[::-1]
			if trail_2 in seen:
				print('YES')
				f = True
				break
	if f:
		continue
	seen = set()
	for s in z:
		if len(s) == 3:
			seen.add(s[:2])
		elif s[::-1] in seen:
			print('YES')
			f = True
			break
	if not f:
		print('NO')


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	ans = 'NO\n'
	count2 = set()
	count3 = set()
	for z in range(n):
		word = input()
		if len(word) == 1:
			ans = 'YES\n'
			continue
		elif len(word) == 3:
			count3.add(word)
			count3.add(word[:2])
			if word[1:][::-1] in count2 or word[::-1] in count3:
				ans = 'YES\n'
				continue
		else:
			count2.add(word)
			if word[::-1] in count2 or word[::-1] in count3:
				ans = 'YES\n'
				continue
	out += ans
print(out)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	s = set()
	f = False
	for i in range(n):
		r = l[i][::-1]
		if len(l[i]) == 1 or r == l[i]:
			f = True
			break
		if r in s or (len(r) == 3 and r[0:2] in s):
			f = True
			break
		if len(l[i]) == 2:
			for c in 'abcdefghijklmnopqrstuvwxyz':
				if r + c in s:
					f = True
					break
		s.add(l[i])
	if not f:
		print('NO')
	else:
		print('YES')


from typing import List, Set

def solve() -> bool:
	n = int(input())
	strings: List[str] = []
	for _ in range(n):
		strings.append(input())
	iterated: Set[str] = set()
	for string in strings:
		if string[0] == string[-1]:
			return True
		if len(string) == 2:
			rev = string[1] + string[0]
			if rev in iterated:
				return True
			for i in range(26):
				_rev = rev + chr(97 + i)
				if _rev in iterated:
					return True
		elif len(string) == 3:
			rev = string[2] + string[1]
			if rev in iterated:
				return True
			rev += string[0]
			if rev in iterated:
				return True
		else:
			raise RuntimeError(f"Shouldn't reach here: len({string}) = {len(string)}")
		iterated.add(string)
	return False
results: List[str] = []
for _ in range(int(input())):
	results.append('YES' if solve() else 'NO')
print('\n'.join(results))


for _ in range(int(input())):
	n = int(input())
	flag = False
	arr = []
	(a, b, c) = ({}, {}, {})
	for i in range(n):
		x = input()
		arr.append(x)
		if len(x) == 1:
			flag = True
		elif len(x) == 2:
			a[x] = i
		elif len(x) == 3:
			b[x] = i
			c[x[1:]] = i
	if flag:
		print('YES')
		continue
	for (i, x) in enumerate(arr):
		flag = False
		if len(x) == 2:
			flag = a.get(x[::-1], -1) >= i or c.get(x[::-1], -1) >= i
		elif len(x) == 3:
			flag = b.get(x[::-1], -1) >= i or a.get(x[1::-1], -1) >= i
		if flag:
			print('YES')
			break
	else:
		print('NO')


def solve_case(n, s):
	d = set()
	for i in s:
		if i == i[::-1]:
			return 'YES'
	for i in s:
		if i[::-1] in d:
			return 'YES'
		if len(i) == 2:
			for j in range(26):
				if i[::-1] + chr(ord('a') + j) in d:
					return 'YES'
		elif i[-2:][::-1] in d:
			return 'YES'
		d.add(i)
	return 'NO'

def solve():
	t = int(input())
	cases = []
	for i in range(t):
		n = int(input())
		s = [input() for i in range(n)]
		cases.append([n, s])
	for case in cases:
		(n, s) = (case[0], case[1])
		print(solve_case(n, s))
solve()


import sys
from math import sqrt, gcd
from collections import deque, Counter
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	(d, d2) = ({}, {})
	flag = 0
	for i in range(n):
		s = S()
		if s == s[::-1]:
			flag = 1
		elif len(s) == 2 and s[::-1] in d:
			flag = 1
		elif len(s) == 3 and (s[::-1] in d or (s[1:3][::-1] in d and s[1:3][::-1] in d2)):
			flag = 1
		if len(s) == 2:
			(d[s], d2[s]) = (1, 1)
		elif len(s) == 3:
			d[s[0:2]] = 1
			d[s] = 1
	print('YES' if flag else 'NO')


def evaluate(a):
	vals = set()
	v = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	for x in a:
		if len(x) == 1:
			return True
		elif len(x) == 2 and x[0] == x[1]:
			return True
		elif len(x) == 3 and x[0] == x[2]:
			return True
		elif len(x) == 2:
			if x[1] + x[0] in vals:
				return True
			for i in v:
				j = x[1] + x[0] + i
				if j in vals:
					return True
			vals.add(x)
		elif len(x) == 3:
			if x[2] + x[1] + x[0] in vals:
				return True
			if x[2] + x[1] in vals:
				return True
			vals.add(x)
	return False
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for x in range(n):
		v = input()
		a.append(v)
	val = evaluate(a)
	if val:
		print('YES')
	else:
		print('NO')


alphabet_in_lowercase = {chr(i) for i in range(97, 123)}
for i in range(int(input())):
	(lis, out, k) = (set(), 'NO', False)
	for j in range(int(input())):
		s = input()
		if not k:
			revs = ''.join(reversed(s))
			if s == revs or revs in lis:
				out = 'YES'
				k = True
			elif lis:
				d = len(s)
				if d == 2:
					for q in alphabet_in_lowercase:
						if revs + q in lis:
							out = 'YES'
							k = True
				else:
					revkey = ''.join(reversed(s[1:]))
					if revkey in lis:
						out = 'YES'
						k = True
		lis.add(s)
	print(out)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [input() for _ in range(n)]
	for e in a:
		if e == ''.join(reversed(e)):
			print('YES')
			break
	else:
		s = set()
		for e in a:
			if ''.join(reversed(e)) in s:
				print('YES')
				break
			s.add(e)
		else:
			s2 = set()
			s3 = set()
			for e in a:
				if len(e) == 2 and ''.join(reversed(e)) in s3:
					print('YES')
					break
				if len(e) == 3 and ''.join(reversed(e[1:])) in s2:
					print('YES')
					break
				if len(e) == 2:
					s2.add(e)
				if len(e) == 3:
					s3.add(e[:2])
			else:
				print('NO')


for _ in range(int(input())):
	flag = False
	m = {}
	mp = {}
	ss = []
	for i in range(int(input())):
		st = input()
		ss.append(st)
	for s in ss:
		if s[0] == s[-1]:
			flag = True
			break
		else:
			m[s] = len(s)
			mp[s] = len(s)
			s_reverse = s
			s_reverse = ''.join(reversed(s_reverse))
			if m.get(s_reverse) == len(s):
				flag = True
				break
			if len(s) == 3:
				s_front = s[0:2]
				s_later = s[1:3]
				s_later = ''.join(reversed(s_later))
				m[s_front] = 2
				if m.get(s_later) == 2 and mp.get(s_later) == 2:
					flag = True
					break
	if flag:
		print('YES')
	else:
		print('NO')
	m.clear()
	mp.clear()


chars = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(int(input())):
	n = int(input())
	s = set()
	for i in range(n):
		t = input()
		if t == t[::-1]:
			print('YES')
			for j in range(i + 1, n):
				input()
			break
		if len(t) == 3 and (t[::-1] in s or t[1:][::-1] in s):
			print('YES')
			for j in range(i + 1, n):
				input()
			break
		if len(t) == 2 and t[::-1] in s:
			print('YES')
			for j in range(i + 1, n):
				input()
			break
		if len(t) == 2:
			found = False
			for c in chars:
				if t[::-1] + c in s:
					print('YES')
					for j in range(i + 1, n):
						input()
					found = True
					break
			if found:
				break
		s.add(t)
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solve():
	for c in s:
		if c[0] == c[-1]:
			print('YES')
			return
	for c in s:
		if len(c) == 2:
			if freq[ord(c[1]) - ord('a')][ord(c[0]) - ord('a')][26]:
				print('YES')
				return
			freq[ord(c[0]) - ord('a')][ord(c[1]) - ord('a')][26] = 2
		else:
			if freq[ord(c[2]) - ord('a')][ord(c[1]) - ord('a')][ord(c[0]) - ord('a')] or freq[ord(c[2]) - ord('a')][ord(c[1]) - ord('a')][26] == 2:
				print('YES')
				return
			freq[ord(c[0]) - ord('a')][ord(c[1]) - ord('a')][26] = max(1, freq[ord(c[0]) - ord('a')][ord(c[1]) - ord('a')][26])
			freq[ord(c[0]) - ord('a')][ord(c[1]) - ord('a')][ord(c[2]) - ord('a')] = 1
	print('NO')
for _ in range(int(input().strip())):
	n = int(input().strip())
	s = []
	for _ in range(n):
		s.append(input().strip())
	freq = [[[0 for _ in range(27)] for _ in range(26)] for _ in range(26)]
	solve()


def main():
	n = int(input())
	ss = [(list(input()), i) for i in range(n)]
	ssr = [(s[::-1], i) for (s, i) in ss]
	ss.sort()
	ssr.sort()
	p1 = 0
	p2 = 0
	while p1 < n and p2 < n:
		(s1, i1) = ss[p1]
		(s2, i2) = ssr[p2]
		ml = min(len(s1), len(s2))
		if s1 == s2 or (i1 < i2 and s1[:ml] == s2[:ml]):
			print('YES')
			return
		if s1 < s2:
			p1 += 1
		else:
			p2 += 1
	print('NO')
for _ in range(int(input())):
	main()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = []
	d = defaultdict(lambda : 0)
	for i in range(n):
		s = input()
		A.append(s)
		d[s] += 1
	ok = False
	for i in range(n):
		o = A[i]
		o = o[::-1]
		if o == o[::-1] or d[o] > 0:
			ok = True
		for j in range(26):
			l = chr(j + 97) + o
			if d[l] > 0:
				ok = True
		if len(o) == 3:
			if d[o[1:]] > 0:
				ok = True
		d[A[i]] -= 1
	if ok:
		print('YES')
	else:
		print('NO')