C. Interesting Operation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an string $$$s$$$ of size $$$n$$$ composed of lowercase letters.

Define $$$f(C)$$$ as the character obtained by shifting the character $$$C$$$ to the left.Formally,$$$f(a)=z,f(b)=a,...,f(z)=y$$$.

You can do the following operation any number of times:

  • choose two different indexes $$$i,j(1 \leq i,j \leq n)$$$,then make $$$s_i:=f(s_i)$$$ and $$$s_j:=f(s_j)$$$;

Find the minimum number of operations to make all characters in $$$s$$$ to $$$a$$$.If you can not make all characters in $$$s$$$ to $$$a$$$,output $$$-1$$$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$).

The second line of each testcase contains a string $$$s$$$ of size $$$n$$$ composed of lowercase letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of operations to make all characters in $$$s$$$ to $$$a$$$.If you can not make all characters in $$$s$$$ to $$$a$$$,output $$$-1$$$ instead.

Example
Input
5
2
aa
2
ab
2
cc
3
amo
4
egzx
Output
0
-1
2
26
29
Note

Test Case $$$1$$$:

All characters in $$$s$$$ are already $$$a$$$ so you don't need to do any operations.

Test Case $$$2$$$:

You can not make all characters in $$$s$$$ to $$$a$$$.

Test Case $$$3$$$:

We use the following scheme: $$$cc\xrightarrow{i=1,j=2} bb\xrightarrow{i=1,j=2} aa$$$.

Test Case $$$4$$$:

We use the following scheme: $$$amo\xrightarrow{i=1,j=2} zlo\xrightarrow{i=1,j=2} yko \xrightarrow{i=1,j=2} ... \xrightarrow{i=1,j=2} oao \xrightarrow{i=1,j=3} nan \xrightarrow{i=1,j=3} mam \xrightarrow{i=1,j=3} ... \xrightarrow{i=1,j=3} aaa$$$.