题目描述

给定一个由小写英文字母组成的字符串 $S$。すぬけ君可以进行如下操作：交换 $S$ 中相邻的两个字符。例如，若 $S=$agc，则一次操作可以将 $S$ 变为 gac（交换 a 和 g），或变为 acg（交换 g 和 c）。

すぬけ君可以重复进行该操作 $0$ 次或多次，目标是使得 $S$ 在字典序上满足 atcoder $< S$。

字典序 $x < y$ 的定义如下：对于字符串 $x, y$，若满足以下任一条件，则称 $x$ 在字典序上小于 $y$：

• 存在某个整数 $i$（$1 \leq i \leq \min(|x|, |y|)$），使得 $x$ 和 $y$ 的前 $i-1$ 个字符相同，且 $x$ 的第 $i$ 个字符在字母表中严格小于 $y$ 的第 $i$ 个字符。
• $|x| < |y|$，且 $y$ 的前 $|x|$ 个字符与 $x$ 完全相同。

请判断目标是否可以达成。如果可以，输出所需操作次数的最小值；如果无法达成，输出 $-1$。

对于每个输入文件，需要解答 $T$ 个测试用例。

输入格式

输入从标准输入读入，格式如下：

$T$

接下来有 $T$ 个测试用例。每个测试用例格式如下：

$S$

输出格式

对于每个测试用例，如果目标无法达成，输出 $-1$；如果可以达成，输出所需操作次数的最小值。每个测试用例输出一行。

样例 1

输入

3
atcodeer
codeforces
aaa

输出

1
0
-1

说明/提示

限制条件

• $1 \leq T \leq 100$
• $1 \leq |S| \leq 1000$
• $S$ 由小写英文字母组成。

样例解释 1

• 第 $1$ 个测试用例：例如，将末尾的 $2$ 个字符交换后，$S=$atcodere $>$ atcoder。
• 第 $2$ 个测试用例：无需任何操作，$S=$codeforces $>$ atcoder。
• 第 $3$ 个测试用例：无论如何操作，都无法使 $S >$ atcoder。

由 ChatGPT 4.1 翻译