问题描述

给定一个由小写英文字母组成的字符串 $S$。Snuke 可以对 $S$ 中的两个相邻字符进行交换操作。例如，如果 $S=$agc，则可以通过交换 a 和 g 将其变为 gac 或者通过交换 g 和 c 将其变为 acg。

Snuke 希望进行零次或多次操作，使得 atcoder $<S$，即按字典序 atcoder 在 $S$ 之前。

字典序 $x < y$ 的定义如下：

对于字符串 $x$ 和 $y$，当且仅当满足以下条件之一时，$x < y$ 在字典序上成立：

• 存在整数 $i$ ($1 \leq i \leq \min(|x|, |y|)$)，使得 $x$ 的前 $i-1$ 个字符与 $y$ 的前 $i-1$ 个字符相等，并且 $x$ 的第 $i$ 个字符在字母表顺序中严格小于 $y$ 的第 $i$ 个字符。
• 满足 $|x| < |y|$，并且 $y$ 的前 $|x|$ 个字符与 $x$ 相等。

确定是否可以达到目标。如果可以达到，找出所需的最小操作次数。

解决输入文件中的 $T$ 个测试用例。

约束条件

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

输入

输入以以下格式从标准输入给出。输入的第一行是：

$T$

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

$S$

输出

对于每个测试用例，如果目标不可达，则打印 $-1$；如果目标可达，则打印所需的最小操作次数。每个测试用例打印一行。

示例输入 1

3
atcodeer
codeforces
aaa

示例输出 1

1
0
-1

• 第一个测试用例：例如，交换最后两个字符可以使得 $S=$atcodere $\>$ atcoder 成立。
• 第二个测试用例：在进行任何操作之前，我们已经有 $S=$codeforces $\>$ atcoder。
• 第三个测试用例：没有任何操作序列可以使 $S>$ atcoder 成立。