Make a Palindrome

시간 제한2초메모리 제한2048 MB

요약

거리가 정확히 2인 두 문자를 맞바꾸는 연산만으로 주어진 문자열을 팰린드롭으로 만들 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 문자열, 수학, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

You have a string $s$ consisting of lowercase English letters. You want to transform it into a palindrome by performing zero or more operations. In one operation, you can swap any two characters in the string which are at distance exactly $2$ from each other (in other words, there is exactly one character between them).

Determine if it is possible to transform the string $s$ into a palindrome.

A palindrome is a string that coincides with its reversed copy.

입력

The first line contains an integer $t$ ( $1 \le t \le 10^5$ ), the number of test cases. The test cases follow.

The first line of each test case contains an integer $n$ ( $1 \le n \le 10^5$ ). The second line contains the string $s$ of length $n$ consisting of lowercase English letters.

The sum of $n$ over all test cases does not exceed $10^5$ .

출력

For each test case, print a line containing "YES" if it is possible to transform the given string into a palindrome by the given rules, or "NO" otherwise.

예제1

예제 1

입력

8
6
acbbca
6
acbbac
6
aaaaaa
7
abcacba
9
abcbcecea
1
b
2
ca
2
cc

예상 출력

YES
NO
YES
YES
YES
YES
NO
YES