You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given a string \(S\) of length \(N\) consisting only lower case letters. Find the number of pivot points of the string \(S\).
Let me describe what the pivot point of a string is. If the i-th index is a pivot point of S then:-

• delete all the occurence of the i-th character from the string except the character in pivot point itself. for example if the string is "ababaac" and the pivot point is 3 then the string will be converted into "babc". because the character in pivot point is 'a', so we have to delete all 'a' except one from the string. this operation can be done only once for a pivot point.

• select any index j (except the pivot point) and delete all the occurence of the j-th character from the string.lets take the string "babc" after first operation, now we select j=3, the character in j-th index is 'b', so we will delete all 'b' from the string. as a result the string becomes "ac". You can do this task zero or any number of times.

• You should end up with a palindrom string of length more than 1. after doing the first operation once and the 2nd operation as many times you want.

print the total number of pivot points the string \(S\) has independently.

A palindrom string in a string which remains same after reversing the string. In another words S==rev(S)
for example: aa, abcba, b, okoko, saippuakivikauppias

Input

first line of input takes an integer T: number of testcases
each testcase takes two lines of input,
first line will take input of an integer N: length of the string S
second line will take input of a string S of length N
1 <= T <= 1000
1 <= N <= 100000
it is guaranteed that the sum of N over all testcase will not exceed 100000

Output

print T lines, each line should consist an integer : the total number of pivot points the string S has.

Sample

3
4
baba
6
abbccd
9
abobacbec

2
0
5

in the first testcase,
index 2 is a pivot point because,
in the pivot point the character is 'a' , so we delete all the occurance of 'a' from the string except the pivot point itself. so the string becomes "bab".
we choose to do the 2nd operation 0 times, so we end up with a palindrome "bab". so the index 2 is a pivot point of the string "baba".

index 3 is also a pivot point, we can end up with a palindrome string "aba" after doing the first operaiton once and 2nd operaion 0 times.

in the second testcase , it can be shown that there are no pivot points in the string

in the third testcase one pivot point is index 2, lets see the process how it is a pivot point.
at first we apply the first operation, delete all the occurance of 'b' from the string except one 'b' in pivot point. so the string becomes "aboacec"
then we apply the second operation 3 times.
first we chose j=3 and delete all 'o' from the string and the string becomes "abacec"
then we chose j=4 and delete all 'c' from the string and the string becomes "abae"
then we chose j=4 and delete all 'e' from the string and the string becomes "aba"
so we are able to achive a palindrome string. so index 2 is a pivot point.

similarly index 3,4,7,8 ar also pivot points of the string "abobacbec"