"was it a car or a cat i saw ?"

palindromes are sequence of characters which looks same if read backward or forward.

Poor Jhonny has AIBOHPHOBIA-phobia of palindromes.
His teacher has given him a homework on palindromes.
Since you are a good programmer and his close friend so he has approached you for help.

Problem goes like this - "There is a string of length N consisting of only lowercase english characters. The task is to find the minimum number of characters to be deleted from the string so that the resulting string after deletion can be rearranged to form a palindrome."

You have to tell the minimum number of deletions required.

Input :

First line will contain an integer T(number of testcases).
Then T blocks of line follows.
Each blocks contain 2 lines
First line contains an integer N(number of characters in string)
Second line contains a string of N characters(lowercase)

Output :

Print on new line the required answer for each input string.

Constraints :

T<=100
N<=200000
String will contain only lowercase letters