Question
Palindrome Flipping
Find if it is possible to convert S to a palindrome by applying the above operation any (possibly zero) number of times.
Note: A string is called a palindrome if it reads the same backwards and forwards, for e.g. 10001 and 0110 are palindromic strings.
Chirag has a binary string S of length N. In one operation, Chirag can:
- Select two indices i and j (1 ≤ i, j ≤ N, i ≠ j) and flip Si and Sj. (i.e. change 0 to 1 and 1 to 0)
Find if it is possible to convert S to a palindrome by applying the above operation any (possibly zero) number of times.
Note: A string is called a palindrome if it reads the same backwards and forwards, for e.g. 10001 and 0110 are palindromic strings.
Input
The first line contains a single integer T - the number of test cases. Then the test cases follow.
The first line of each test case contains an integer N - the length of the binary string S.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 105
S contains 0 and 1 only.
Sum of N over all test cases does not exceed 2x105
The first line of each test case contains an integer N - the length of the binary string S.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 105
S contains 0 and 1 only.
Sum of N over all test cases does not exceed 2x105
Output
For each test case, output Yes if it is possible to convert S to a palindrome. Otherwise, output No.
Example
Sample Input
2
6
101011
2
01
Sample Output
Yes
No
Explanation
Test case 1: We can perform the following operation:
Select i = 3 and j = 5. Then 101011 → 100001, which is a palindrome.
Test case 2: It can be proven that we can not make S a palindrome using the given operation.
2
6
101011
2
01
Sample Output
Yes
No
Explanation
Test case 1: We can perform the following operation:
Select i = 3 and j = 5. Then 101011 → 100001, which is a palindrome.
Test case 2: It can be proven that we can not make S a palindrome using the given operation.