说明

给定一个字符串长度为$n$的字符串$s$为$s_1s_2s_3...s_n$，我们定义$s$的左旋串为$s_2s_3...s_ns_1$，$s$的右旋串为$s_ns_1....s_{n-1}$，对于一个串$s$满足旋转串的条件是这个串的左旋串和右旋串相同，给定一个字符串$s$，现在想知道至少删掉几个字符可以让其变成旋转串。

输入格式

第一行一个整数$t$表示数据组数。

接下来$t$行每行一个字符串$s$。

输出格式

$t​$行每行一个整数表示最少需要删掉的字符数。

样例

2
123
12121212

1
0

提示

数据范围

对于 $30\%$ 的数据，$1 \le n \le 10$。

对于 $50\%$ 的数据，$1 \le n \le 10^3$。

对于 $100\%$ 的数据，$ 1 \le t \le 10, 1 \le n \le 10^5$，字符串只包含字符0-9。