You are given a string S containing only lowercase characters. 
You can rearrange the string and you have to print minimum number of characters needed(can be 0) to make it palindrome.

-----Input:-----
- First line contain an interger T denoting number of testcases.
- First line of each testcase contains integer N, size of string.
- Second line of each testcase contains string S.

-----Output:-----
For each test case, print a single line containing one integer ― the minimum number of characters needed(can be 0) to make it palindrome.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^5$

-----Sample Input:-----
3
1
a
9
abbbcbddd
6
abcdef

-----Sample Output:-----
0
2
5

-----EXPLANATION:-----
- Example case 1: a is already a palindrome.
- Example case 2: abbddcddbba is palindrome by adding 2 more characters.
- Example case 3: abdefcfedba is palindrome by adding 5 more characters.

Difficulty: interview

Starter code:

Solutions:
# cooking dish here

from sys import stdin
from collections import Counter
read = stdin.readline

for testcase in range(int(read())):
    length = int(read())
    string = read().strip()
    
    counts = Counter(string)
    
    odd_counts = 0
    
    for count in list(counts.values()):
        # print(count, counts)
        odd_counts += count%2
        
    print(max(odd_counts-1, 0))


t = int(input())

for j in range(t):
    c = 0 
    f = 1
    k = 0
    n = int(input())
    s = input()
    di = {}
    for i in range(n):
        if(s[i] in di.keys()):
            di[s[i]] = di[s[i]] + 1
        else:
            di[s[i]] = 1
    for i in di.keys():
        if(di[i] == 1 and f):
            f = 0
        elif(di[i]%2 == 1):
            k = 1
            c = c + 1
    if(f and k):
        c = c - 1
    print(c)

from collections import Counter
for _ in range(int(input())):
    lens = int(input())
    inps = input().strip()
    need = 0
    cinps = Counter(inps)
    hasOne = False
    for i in cinps:
        if cinps[i]%2 == 1:
            if hasOne == False:
                hasOne = True
                continue
            else:
                need += 1
    print(need)






try:
    t=int(input())
    for _ in range(t):
        n=int(input())
        s=input()
        i,res=0,0
        dp=[0]*26
        for i in range(n):
            dp[ord(s[i])-97]+=1
        for i in range(26):
            if(dp[i]%2==1):
                res+=1
        if res>0:
            res-=1
        print(res)
except EOFError:
    pass

t = int(input())

for j in range(t):
    c = 0 
    f = 1
    k = 0
    n = int(input())
    s = input()
    di = {}
    for i in range(n):
        if(s[i] in di.keys()):
            di[s[i]] = di[s[i]] + 1
        else:
            di[s[i]] = 1
    for i in di.keys():
        if(di[i] == 1 and f):
            f = 0
        elif(di[i]%2 == 1):
            k = 1
            c = c + 1
    if(f and k):
        c = c - 1
    print(c)

#Code goes here!
from collections import Counter
for i in range(int(input())):
    n = int(input())
    a = input().strip()
    lst = list(Counter(a).values())
    odds_count = sum([1 for x in lst if x%2!=0])
    if odds_count>1:
        print(odds_count-1)
    else:
        print(0)

#Code goes here!
from collections import Counter
for i in range(int(input())):
    n = int(input())
    a = input().strip()
    cnt = 0

    if a == a[::-1]:
        print(cnt)

    else:
        lst = list(Counter(a).values())
        odds_count = sum([1 for x in lst if x%2!=0])
        if odds_count>1:
            print(odds_count-1)
        else:
            print(cnt)

from sys import stdin,stdout
import math,bisect
from datetime import date
from collections import Counter,deque,defaultdict
L=lambda:list(map(int, stdin.readline().strip().split()))
M=lambda:list(map(int, stdin.readline().strip().split()))
I=lambda:int(stdin.readline().strip())
S=lambda:stdin.readline().strip()
C=lambda:stdin.readline().strip().split()
def pr(a):return("".join(list(map(str,a))))
#_________________________________________________#

def solve():
    n = I()
    a = S()
    d=Counter(a)
    ans=0
    for i in d:
        if d[i]%2:
            ans+=1
    print(max(0,ans-1))
    
for _ in range(I()): 
    solve()


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353
def inp(): return stdin.readline().strip()
def out(var, end="\n"): stdout.write(str(var)+"\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return map(int, inp().split())
def smp(): return map(str, inp().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
def remadd(x, y): return 1 if x%y else 0
def ceil(a,b): return (a+b-1)//b

def isprime(x):
    if x<=1: return False
    if x in (2, 3): return True
    if x%2 == 0: return False
    for i in range(3, int(sqrt(x))+1, 2):
        if x%i == 0: return False
    return True

for _ in range(int(inp())):
    n = int(inp())
    s = inp()
    md = {}
    for i in s:
        if i in md: md[i]+=1
        else: md[i]=1
    o, e = 0, 0
    for i in md.values():
        if i%2: o+=1
        else: e+=1
    print(max(o-1, 0))

# cook your dish here
def my_fun():
    return 0
from collections import defaultdict
t=int(input())
for _ in range(t):
    count=0
    n=int(input())
    s=input()
    hm=dict()
    for i in range(n):
        hm[s[i]]=hm.get(s[i],0)+1
    if n%2!=0:
        flag=0
        for key,value in list(hm.items()):
            if value%2!=0 and flag!=1:
                flag=1
            elif value%2!=0 and flag==1:
                count+=1
    else:
            for key,value in list(hm.items()):
                if value%2!=0:
                    count+=1
            if count!=0:
                count-=1
        
    print(count)
        


for _ in range(int(input())):
    n=int(input())
    s=input()
    if s==s[::-1]:
        print(0)
    else:
        an=0
        ar=[0]*26
        for i in range(n):
            ar[ord(s[i])-97]+=1
        for i in range(26):
            if ar[i]%2!=0:
                an+=1
        if an==0:
            print(0)
        else:
            print(an-1)


for _ in range(int(input())):
    n = int(input())
    s = input()
    dic = dict()
    for i in range(n):
        dic[s[i]] = dic.setdefault(s[i], 0) + 1
    ans = 0
    for i in dic:
        if dic[i] % 2 != 0:
            ans += 1
    print(ans - 1 if ans > 0 else ans)


from collections import Counter

for _ in range(int(input())):
    n = int(input())
    s = input().strip()

    c = Counter(s)

    odd = 0
    for i in c:
        if c[i] % 2:
            odd += 1

    if odd > 1:
        print(odd - 1)
    else:
        print(0)