Ashley likes playing with strings.

She gives Mojo a fun problem to solve. In her imaginary string world, a string of even length is called as "Doublindrome" if both halves of the string are palindromes (both halves have length equal to half of original string).

She gives Mojo a string and asks him if he can form a "Doublindrome" by rearranging the characters of the given string or keeping the string as it is.

As Mojo is busy playing with cats, solve the problem for him.

Print "YES" (without quotes) if given string can be rearranged to form a "Doublindrome" else print "NO" (without quotes).

-----Input:-----
- First line will contain a single integer $T$, the number of testcases. 
- Each testcase consists of two lines, first line consists of an integer $N$ (length of the string) and second line consists of  the string $S$. 

-----Output:-----
For each testcase, print "YES"(without quotes) or "NO"(without quotes) on a new line.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 100$
- $N$ is always even.
- String $S$ consists only of lowercase English alphabets.

-----Sample Input:-----
1
8
abbacddc

-----Sample Output:-----
YES

-----EXPLANATION:-----
The given string is a Doublindrome as its 2 halves "abba" and "cddc" are palindromes.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 n=int(input())
 s=input()
 d={}
 for j in s:
  if j not in d:
   d[j]=1
  else:
   d[j]+=1
 f=0
 for j in d:
  if(d[j]%2==1):
   f=f+1
 if((n//2)%2==0 and f==0):
  print("YES")
  continue
 if((n//2)%2==1 and f<=2 and f%2==0):
  print("YES")
  continue
 print("NO")

T = int(input())

for _ in range(T):
 N = int(input())
 S = input()

 if N <= 2:
  print("YES")

 else:
  unique_c = {}
  for c in S:
   if c in list(unique_c.keys()):
    unique_c[c] += 1
   else:
    unique_c[c] = 1
  safe = 0
  no_odd = 0
  for c in list(unique_c.keys()):
   if unique_c[c] % 2 != 0:
    no_odd += 1
  
  if N // 2 % 2 == 1:
   if no_odd == 2 or no_odd == 0:
    print("YES")
   else:
    print("NO")
  else:
   if no_odd != 0:
    print("NO")
   else:
    print("YES")
    


# cook your dish here
try:
 
 t=int(input())
 for i in range(t):
  n=int(input())
  s=input()
  flag=1
  d=dict()
  for j in range(n):
   d[s[j]]=0
  for j in range(n):
   d[s[j]]=d[s[j]]+1
  flag=1
  if (n//2)%2==0:
   for j in list(d.keys()):
    if d[j]%2!=0:
     flag=0
     break
   if flag==1:
    print("YES")
   else:
    print("NO")
  else:
   count=0
   for j in list(d.keys()):
    if d[j]%2!=0:
     count=count+1
    
   if count==2 or count==0:
    print("YES")
   else:
    print("NO")
   
   
     
except:
 pass


from collections import defaultdict

for t in range(int(input())):
 n = int(input())
 s = input()
 d = defaultdict(int)
 for i in s:
  d[i] += 1
 count = 0
 for i,j in d.items():
  if j % 2 == 1:
   count += 1
 # print(count)
 if (n//2) % 2 == 0:
  if count == 0:
   print("YES")
  else:
   print("NO")
 else:
  if count == 2 or count == 0:
   print("YES")
  else:
   print("NO")

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 s=list(input())
 d=dict()
 for i in s:
  d[i]=d.get(i,0)+1
 # print(d.values())
 if (n//2)%2==0:
  for i in list(d.values()):
   if i%2==1:
    print("NO")
    break
  else:
   print("YES")
 else:
  c=0
  for i in list(d.values()):
   if i%2==1:
    c+=1
    if c==3:
     print("NO")
     break
  else:
   print("YES")
   


for t in range(int(input())):
 n = int(input()) // 2
 s = input()
 d = {}
 for i in s:
  if (i not in d):
   d[i] = 0
  d[i] += 1
 res = 0
 for i in d:
  if (d[i] % 2):
   res += 1
 if (n % 2):
  if (res == 0 or res == 2):
   print("YES")
  else:
   print("NO")
 else:
  if (res == 0):
   print("YES")
  else:
   print("NO")