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

Abid has a string \(S\) of length \(N\) containing only lowercase latin letters. He loves his string so much and cannot be happy if someone touches his string.

At this moment Abid is not at home, so his naughty younger brother Abidur makes a plan to make a small change in his string. He will select two distinct index i,j and swap the i-th and j-th character of the string bearing in mind that the string must be same after the operation so that his elder brother cannot guess any change in the string.

Your task is to tell Abidur, how many ways he can pick such a pair \((i,j)\) so that after swapping the \(i\)-th and \(j\)-th index the string remains same as before.

note: \((1,2)\) and \((2,1)\) is considered as two different pair.

Input

first line of input takes an integer \(T\) : number of testcases
first line of each testcase takes an integer \(N\) : length of the string
second line of each testcase takes string \(S\) of length \(N\)
\(1 \le T \le 10^3\)
\(1 \le N \le 10^6\)
sum of \(N\) over all testcase will not exceed \(10^6\)

Output

print one integer in each of the \(T\) line of output : number of possible pairs of i,j

Sample

2
1
a
4
abab

0
4

testcase 1: its not possible to make a pair with just one index
testcase 2: all possible pairs for the case is (1,3) (2,4) (3,1) (4,2)