左移

题目描述

如果一个字符串的第一个字符与最后一个字符相同，我们就说这个字符串很美。

给定长度为 $n$ 的字符串 $S = s_0s_1\cdots s_{n-1}$ ，设 $f(S, d)$ 是将 $S$ 向左移动 $d$ 次得到的字符串。即 $f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}$ 。求能使 $f(S, d)$ 优美的最小非负整数 $d$ 。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$ 表示测试用例的数量。对于每个测试用例

第一行也是唯一一行包含一个仅由英文字母组成的字符串 $s_0s_1\cdots s_{n-1}$ ( $1 \le n \le 5 \times 10^5$ )。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$ 。

输出格式

对于每个测试用例，输出一行包含一个整数的数据，指出最小的非负整数 $d$ ，这样 $f(S, d)$ 是美丽的。如果不可能找到这样的 $d$ ，则输出 -1 代替。

样例 #1

样例输入 #1

4
helloccpc
abcdcba
x
abc

样例输出 #1

3
0
0
-1

提示

第一个示例测试用例是 $f(S, 3) =$ loccpchel。由于它的第一个和最后一个字符都是 l，因此是一个优美的字符串。虽然 $f(S, 6) =$ cpchelloc 也很美，但我们需要回答最小的非负 $d$ 。因此答案是 $3$ 。