A. Turtle and Good Strings

time limit per test

1 second

memory limit per test

256 megabytes

Turtle thinks a string ss is a good string if there exists a sequence of strings t1,t2,…,tkt1,t2,…,tk (kk is an arbitrary integer) such that:

• k≥2k≥2.
• s=t1+t2+…+tks=t1+t2+…+tk, where ++ represents the concatenation operation. For example, abc=a+bcabc=a+bc.
• For all 1≤i<j≤k1≤i<j≤k, the first character of titi isn't equal to the last character of tjtj.

Turtle is given a string ss consisting of lowercase Latin letters. Please tell him whether the string ss is a good string!

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤5001≤t≤500). The description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤1002≤n≤100) — the length of the string.

The second line of each test case contains a string ss of length nn, consisting of lowercase Latin letters.

Output

For each test case, output "YES" if the string ss is a good string, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example

Input

Copy

4

2

aa

3

aba

4

abcb

12

abcabcabcabc

Output

Copy

No
nO
Yes
YES

Note

In the first test case, the sequence of strings a,aa,a satisfies the condition s=t1+t2+…+tks=t1+t2+…+tk, but the first character of t1t1 is equal to the last character of t2t2. It can be seen that there doesn't exist any sequence of strings which satisfies all of the conditions, so the answer is "NO".

In the third test case, the sequence of strings ab,cbab,cb satisfies all of the conditions.

In the fourth test case, the sequence of strings abca,bcab,cabcabca,bcab,cabc satisfies all of the conditions.

解题说明：水题，直接拆成两个字符串，然后比较首尾是否一致，如果一致就不存在了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int T, n;
string s;

int main() 
{
	cin >> T;
	while (T--)
	{
		cin >> n >> s;
		if (s[0] == s[n - 1])
		{
			puts("NO");
		}
		else
		{
			puts("YES");
		}
	}
	return 0;
}