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.

Problem solving instructions ： This problem is a simulation problem , Analyzing the meaning of the question, we can find that as long as the length exceeds 3 It is impossible to meet the requirements , When the length is 2 You must also ensure that the two numbers are not consistent .

#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;
}