在一个神秘的字母王国，所有的字母都有其独特的魅力。**每当一个字符串的第一个字符和最后一个字符相同时，它就被称为“美丽的”**。这个王国的居民们喜欢通过旋转字符串来寻找美丽的字符串。

给定一个长度为 n 的字符串 S = s_0 s_1 \ldots s_{n-1}，定义一个操作 f(S, d) 表示将字符串 S 向左旋转 d 次后得到的新字符串。具体来说，f(S, d) = s_{(d+0) \mod n} s_{(d+1) \mod n} \ldots s_{(d+n-1) \mod n}。

你需要找出最小的非负整数 d，使得 f(S, d) 是美丽的。如果不存在这样的 d，则输出 `-1`。

第一行输入一个仅由小写英文字母组成的字符串 s_0 s_1 \ldots s_{n-1} (1 \leq n \leq 5 \times 10^5)。

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

解释1

f(S, 3) = \text{nmddxdagn}。由于它的第一个字符和最后一个字符都是 n，因此它是一个美丽的字符串。虽然 f(S, 6) = \text{dxdagnnmd} 也是美丽的，但我们需要返回最小的非负整数 d。所以答案是 3。

数据范围与约定

- 对于 30\% 的数据，n \leq 13

- 对于 50\% 的数据，n \leq 5 \times 10^4

- 对于 100\% 的数据，1 \leq n \leq 2 \times 10^6