题目描述

给定一个由小写字母组成的字符串，称该字符串是美丽的，若字符串中每一对相邻的字符都不相同。例如，$\texttt{icpc}$ 和 $\texttt{kunming}$ 是美丽的，但 $\texttt{hello}$ 不是，因为它的第 $3$ 个和第 $4$ 个字符相同。

给定由小写英文字母组成的，长度为 $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}$。

令 $g(S, d)$ 表示将 $f(S, d)$ 变得美丽的最小操作次数。每次操作中，您可以将 $f(S, d)$ 中的任意一个字符改为任意小写字母。

找到一个非负整数 $d$ 最小化 $g(S, d)$，并输出这个最小化的值。

输入格式

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

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

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

输出格式

每组数据输出一行一个整数，表示最小的 $g(S, d)$。

3
abccbbbbd
abcde
x

2
0
0

提示

对于第一组样例数据，考虑 $d = 5$。有 $f(S, 5) =$ $\texttt{bbbdabccb}$。对于这个字符串，我们可以将它的第 $2$ 个字符改成 $\texttt{x}$，并将它的第 $8$ 个字符改成 $\texttt{y}$。这样字符串就会变成 $\texttt{bxbdabcyb}$，是一个美丽的字符串。