说明

时间限制：1 Sec 内存限制：256 MB 输入文件：string.in 输出文件：string.out

一个完全由小写字母组成的字符串 $s$，如果每个字符都和它右边的字符相同，或者与它右边的字符相比在字母表里更靠前，那 $s$ 就是有序的。例如，eee、abc 都是有序的，但 cab 不是。

现在可以做这样的操作：从 $s$ 中选取字典序最大的子序列，将其循环右移一次。

请问，至少要做多少次上述操作才能将 $s$ 变为有序的？

【注】从字符串 $s$ 中任意挑选 $0$ 个或多个字符（可以不相邻）并删除后，留下的部分叫做 $s$ 的子序列。

【注】将字符串 $t_1t_2\cdots t_m$ 循环右移一次，得到的字符串为 $t_mt_1\cdots t_{m-1}$。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来有 $t$ 行，每行为一个完全由小写字母组成的字符串 $s$，第 $i$ 行为第 $i$ 组询问。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个正数，表示至少需要做多少次题目所述的操作才能将 $s$ 变为有序的。如果不可能变为有序的，输出 -1。

样例

样例 1

6
aaabc
acb
bac
zbca
czddeneeeemigec
cdefmopqsvxzz

0
1
-1
2
6
0

样例说明：

第 $1$ 组询问：$s$ 已经是有序的，不需要做操作；

第 $2$ 组询问：acb → abc，共 $1$ 步；

第 $3$ 组询问：bac → bac → bac → ……，无法变为有序的；

第 $4$ 组询问：zbca → abzc → abcz，共 $2$ 步；

第 $5$ 组询问：czddeneeeemigec → ccddezeeeenmige → ccddeeeeeeznmig → ccddeeeeeegznmi → ccddeeeeeegiznm → ccddeeeeeegimzn → ccddeeeeeegimnz，共 $6$ 步；

第 $6$ 组询问：$s$ 已经是有序的，不需要做操作。

数据范围

$1 \le t \le 10^4$

令 $|s|$ 表示字符串 $s$ 的长度，有 $1 \le |s| \le 2 \times 10^5$

题目保证所有的 $|s|$ 之和不超过 $2 \times 10^5$