如果一个字符串的首字符与末字符相同，我们称该字符串是“美丽的”。

给定一个长度为 $n$ 的字符串 $S = s_0s_1 \dots s_{n-1}$，令 $f(S, d)$ 为将 $S$ 向左循环移动 $d$ 次后得到的字符串。即 $f(S, d) = s_{(d+0) \bmod n} s_{(d+1) \bmod n} \dots s_{(d+n-1) \bmod n}$。请找到最小的非负整数 $d$，使得 $f(S, d)$ 是美丽的。

输入格式

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

第一行包含一个字符串 $s_0s_1 \dots s_{n-1}$ ($1 \le n \le 5 \times 10^5$)，仅由小写英文字母组成。

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

输出格式

对于每组测试数据，输出一行，包含一个整数，表示使得 $f(S, d)$ 为美丽的最小非负整数 $d$。如果不存在这样的 $d$，则输出 -1。

样例

输入样例 1

4
helloccpc
abcdcba
x
abc

输出样例 1

3
0
0
-1

说明

对于第一个样例， $f(S, 3) = \text{loccpchel}$。由于其首字符和末字符均为 $\text{l}$，因此它是一个美丽的字符串。虽然 $f(S, 6) = \text{cpchelloc}$ 也是美丽的，但我们需要回答最小的非负整数 $d$，因此答案是 3。