#P0107. 回文串判断

回文串判断

马科斯非常喜欢字符串,所以他有一个最喜欢的字符串,该字符串由小写英文字母组成。对于这个字符串,他在一张纸上以任意顺序写下了它所有的非空前缀和非空后缀(不包含字符串自身)。你看到了纸上的所有这些字符串,需要判断马科斯最喜欢的这个字符串是否是一个回文。

回文定义:如果一个字符串从头到尾读起来和从尾到头读起来是一样的,那么它就是一个回文。 例如,gg、ioi、abba、icpci 是回文;codeforces、abcd、alt 不是回文。

输入格式

  1. 第一行包含一个整数 tt(1≤t≤1201 \le t \le 120)—— 测试用例的数量。
  2. 每个测试用例的描述:
    • 第一行包含一个整数 nn(2≤n≤202 \le n \le 20)—— 字符串 ss 的长度。
    • 第二行包含 2n−22n-2 个字符串 a1,a2,…,a2n−2a_1, a_2, \dots, a_{2n-2} —— 字符串 ss 的所有非空前缀和非空后缀的组合(除自身),顺序任意。

保证:输入的所有字符串都是某个由小写英文字母组成的字符串的非空前缀和后缀。

输出格式

对于每个测试用例,如果字符串 ss 是回文,输出 Yes,否则输出 No。

注意:必须是严格意义大小写上的Yes或者No,形如YES,NO,YeS等都不对

示例输入输出

输入

5
4
bcd cd a d abc ab
3
i io i oi
2
g g
3
t al lt a
4
bba a ab a abb ba

输出

No
Yes
Yes
No
Yes

注意事项

  1. 第一个测试用例中,原字符串 ss 是 abcd: 其非空前缀为 a、ab、abc,非空后缀为 d、cd、bcd;因 abcd 不是回文,故输出 NO。
  2. 第二个测试用例中,原字符串 ss 是 ioi: 其非空前缀为 i、io,非空后缀为 i、oi;因 ioi 是回文,故输出 YES。