题目描述

称一个字符串是美丽的，若它的第一个字符和最后一个字符相同。

给定长度为 $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}$。求最小的非负整数 $d$ 满足 $f(S, d)$ 是美丽的。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个仅由小写英文字母组成的字符串 $s_0s_1\cdots s_{n-1}$（$1 \le n \le 5 \times 10^5$）。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

输出格式

每组数据输出一行一个整数，表示满足 $f(S, d)$ 是美丽的最小非负整数 $d$。若不存在这样的 $d$，输出 $\texttt{-1}$。

4
helloccpc
abcdcba
x
abc

3
0
0
-1

提示

对于第一组样例数据，$f(S, 3) = \texttt{loccpchel}$。它的第一个字符和最后一个字符都是 $\texttt{l}$，所以它是一个美丽字符串。虽然 $f(S, 6) = \texttt{cpchelloc}$ 也是美丽的，我们需要回答最小的非负整数 $d$。所以答案是 $3$。