A. ABC

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string ss as input. However, they soon found out that if some substring tt of ss is a palindrome of length greater than 1, the algorithm will work incorrectly. Can the students somehow reorder the characters of ss so that the algorithm will work correctly on the string?

A binary string is a string where each character is either 0 or 1.

A string aa is a substring of a string bb if aa can be obtained from bb by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A palindrome is a string that reads the same backwards as forwards.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001≤t≤100). Description of the test cases follows.

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

The second line of each test case contains the string ss of length nn consisting only of the characters 0 and 1.

Output

For each test case, print YES (case-insensitive) if it is possible to reorder the characters of ss so that there are no substrings that are a palindrome of length greater than 1, or NO (case-insensitive) otherwise.

Example

input

Copy

4
1
1
2
10
2
01
4
1010

output

Copy

YES
YES
YES
NO

Note

In the first three test cases, the given strings do not contain palindromes of length greater than 1, so the answers are YES.

In the last test case, it is impossible to reorder the characters so that the string does not contain palindromes of length greater than 1, so the answer is NO.

解题说明：此题是一道模拟题，分析题意能发现只要长度超过3就不可能满足要求，当长度为2时也必须确保两个数不一致。

#include <stdio.h>

char s[107];

int main() 
{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) 
	{
		int n;
		scanf("%d", &n);
		scanf("%s", &s[1]);
		if (n == 1 || (n == 2 && s[1] != s[2]))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}