解题思路

设字符串为 $s$，若 $i<j$ 且 $s_i>s_j$，则 $(i,j)$ 是一个不稳定对。题目本质上就是：

• 先求字符串原本的逆序对数量；
• 再考虑一次操作对逆序对数量的影响，求最大增量。

核心思路

题目内容

给定一个长度为 $n$ 的仅由小写字母组成的字符串 $s$（下标从 $1$ 开始），定义当且仅当 $i<j$ 且 s_i​ 在字母表中严格晚于 $s_j$​ 时，($i,j$) 构成一个不稳定对。字符串的不稳定值是其中所有不稳定对的数量。

你可以进行以下操作最多一次：

选择两个不同的下标 $i<j$，将 $s_i$​ 循环替换为其下一个字母（特别地，$z$ 的下一个字母是 $a$），同时将 $s_j$​ 循环替换为其上一个字母（特别地，$a$ 的上一个字母是 $z$）。

请输出经过至多一次操作后能够达到的最大不稳定值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1≤T≤10^4)$，表示数据组数。每组测试数据格式如下：

第一行输入一个整数 $n (2≤n≤2×10^5)$，表示字符串长度；

第二行输入一个长度为 $n$ 的字符串 $s$，仅由小写字母构成。

除此之外，保证所有测试数据的 $n$ 之和不超过 $2×10^5$。

输出描述

对于每组测试数据，输出一个整数，表示能获得的最大不稳定值。

样例1

输入

2
4
zzzz
3
cba

输出

4
3

说明

• 对于第一个样例选择 $i=3,j=4$ 修改后字符串变为 $zzay$。

• 第二个样例不操作即为最大值。