米海打算看电影。他只喜欢回文电影,所以他想跳过一些(可能是零)场景,使电影的其余部分成为回文。
给你一个 $$$s$$$ 的列表,其中包含 $$$n$$$ 个非空字符串,长度最多为 $$$3$$$,代表 Mihai 电影中的场景。
如果 $$$s$$$ 的子序列非空,并且子序列中字符串的按顺序连接是回文,则该子序列被称为 Awesome。
你能帮 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$$$。
输出
对于每个测试用例,如果存在 $$$s$$$ 的精彩子序列,则打印“YES”,否则打印“NO”(不区分大小写)。
示例
输入 #1
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
输出 #1
YES NO NO YES YES NO
注意
在第一个测试用例中, $$$s$$$ 的一个很棒的子序列是 $$$[ab, cc, ba]$$$