Peculiar Movie Preferences

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 ss of nn non-empty strings of length at most 33, representing the scenes of Mihai’s movie.

A subsequence of ss 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 ss?

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 aa is a non-empty subsequence of a non-empty sequence bb if aa can be obtained from bb by deletion of several (possibly zero, but not all) elements.

Input

The first line of the input contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105) — the number of scenes in the movie.

Then follows nn lines, the ii-th of which containing a single non-empty string sisi of length at most 33, consisting of lowercase Latin letters.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case, print “YES” if there is an awesome subsequence of ss, or “NO” otherwise (case insensitive).

Example

input

Copy

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

Copy

YES
NO
NO
YES
YES
NO

Note

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

思路：首先这个题是有顺序要求的，如样例2：ab，bad，如果不按顺序是能组成回文字符串的，badab是回文，但是结果却是NO，所以是有顺序要求的：我们只需要将每个字符处理为真，处理过的再去掉。遍历处理过的就不能在处理对比，否则就会将两个字符的顺序颠倒。回文字符串的操作：是要以字符串为整体来操作的。外面只需要在套个循环就能实现比对。对比需要用“哈希”，判断是否为真。比对时需要用长的与短的对比。（如果用短的与长的对比，还得将长的提取出，然后再对比，长的先出现还是后出现不好判断不好处理，增加太多无用操作导致代码会出现很多错误）。长度为1的与字符串全相同的必为真。对于长度为2的其实它们是不分先后顺序的，分顺序也无所谓，不管谁先谁后依然是回文。也就剩下长度2与2，2与3，3与3，3与2.长度相同的只需要反转看后面有相同的没有。2与3的是2先，我们让3找2，所以先将2的加一个变量留下即可，3与2的直接让3的往后找有没有即可。

reverse：不能用变量接收，所以要先加额外变量接收提取的字符。（（后面）用“哈希”的，原来的字符不能改变，需加变量）

字符串的比较（排序）：是按照字典序比较的，长短不一也是先比较字典序的。比较全相同的才会返回较短的。

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

#define len(x) x.size()
//#define reverse(x) reverse(x.begin(),x.end())

const int N=1e5+10;
string s[N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        bool ok=false;
        map<string,int>two,three;
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
            three[s[i]]++;
            if(len(s[i])==1) ok=true;
            else if(len(s[i])==2)
            {
                if(s[i][0]==s[i][1])ok=true;
            }
            else
            {
                if(s[i][0]==s[i][1]&&s[i][1]==s[i][2])ok= true;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(len(s[i])==2)
            {
                two[s[i]]++;

                string x=s[i];
                reverse(x.begin(),x.end());
                if(two[x])ok=true;
            }


            else if(len(s[i])==3)
            {
                string x=s[i];
                reverse(x.begin(),x.end());
                if(three[x])ok=true;


                string t1="";
                string t2="";
                t1+=s[i][1];
                t1+=s[i][2];
                t2+=s[i][0];
                t2+=s[i][1];
                reverse(t1.begin(),t1.end());
                reverse(t2.begin(),t2.end());
                if(two[t1]||three[t2])ok=true;
            }
            three[s[i]]--;
        }
        if(ok)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}