题目内容

给定一个长度为 $n$ 的仅由小写字母组成的序列 $s$（下标从 $1$ 开始）。对于 $i<j$，若 $s_i$ 在字母表中严格晚于 $s_j$，则称 $(i,j)$ 为一个 "冲突对"。序列的 "冲突度" 定义为冲突对的总数。

你至多可以执行一次如下操作：选择两个不同的下标 $i<j$，将 $s_i$ 循环替换为其下一个字母（$z$ 的下一个字母是 $a$），将 $s_j$ 循环替换为其上一个字母（$a$ 的上一个字母是 $z$）。

请你求出经过至多一次操作后，序列冲突度能够达到的最大值。

数据组数不超过 10^4，每组的字符串长度 n 满足 2 ≤ n ≤ 2×10^5，所有组的 n 之和不超过 2×10^5。字符串 $s$ 仅由小写字母组成。

输入描述

第一行包含一个整数 $T$，表示测试案例的数量。 对于每个测试案例： 第一行包含一个整数 $n$，表示序列长度。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写字母组成。

输出描述

对于每个测试案例，输出一个整数，表示经过至多一次操作后能获得的最大冲突度。

样例1

输入

4
2
ab
2
az
3
acb
3
bca

输出

1
0
2
3

说明

样例1：初始序列 ab，冲突度为 0（因为 $a < b$）。选择 $i=1, j=2$ 进行操作，$s_1$ 由 $a$ 变为 $b$（$a \to b$），$s_2$ 由 $b$ 变为 $a$（$b \to a$），得到序列 ba。ba 中 $(1,2)$ 构成一个冲突对，冲突度变为 1。不操作时冲突度为 0，因此至多一次操作后能获得的最大冲突度为 1。

样例2：初始序列 az，冲突度为 0。唯一可能的操作是选择 $i=1, j=2$，将 $s_1$ 由 $a$ 变为 $b$，$s_2$ 由 $z$ 变为 $y$，得到序列 by。$b < y$，无冲突对，冲突度仍为 0，故最大冲突度为 0。

样例3：初始序列 acb（$a, c, b$）。检查所有对：$(1,2): a<c$，不冲突；$(1,3): a<b$，不冲突；$(2,3): c>b$，冲突。初始冲突度为 1。若选择 $i=1, j=3$ 操作，$a\to b$, $b\to a$，序列变为 bca。此时冲突对有 $(1,3): b>a$ 和 $(2,3): c>a$，冲突度增至 2。其他操作（如 $i=1, j=2$ 得 bbb，冲突度 0；$i=2, j=3$ 得 ada，冲突度 1）均不超过 2。故最大冲突度为 2。

样例4：初始序列 bca。冲突对：$(1,3): b>a$ 和 $(2,3): c>a$，初始冲突度 2。选择 $i=1, j=2$ 操作：$b\to c$, $c\to b$，序列变为 cba。cba 中 $c>b$, $c>a$, $b>a$ 全部冲突，冲突度达到 3。其他操作会导致冲突度不变或减少。故最大冲突度为 3。