让我们将某个字符串 $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ 的左循环移位称为字符串 $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$。
类似地,我们将字符串 $$$t$$$ 的右循环移位称为字符串 $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$。
假设字符串 $$$t$$$ 是好的,如果它的左循环移位等于它的右循环移位。
给定字符串 $$$s$$$,其中包含数字 0–9。
您需要从 $$$s$$$ 中删除至少多少个字符才能使其正常?
输入
第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行包含测试用例 - 每行一个。每个测试用例的第一行也是唯一一行包含字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$)。每个字符 $$$s_i$$$ 是数字 0–9。
保证字符串总长度不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印您需要从 $$$s$$$ 中删除的最少字符数以使其正常。
示例
输入 #1
3 95831 100120013 252525252525
输出 #1
3 5 0
注意
在第一个测试用例中,您可以删除任何 $$$3$$$ 字符,例如 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th。你会得到字符串 51,它很好。
在第二个测试用例中,我们可以删除除 0 之外的所有字符:剩余的字符串为 0000,这很好。
在第三个测试用例中,给定的字符串 $$$s$$$ 已经很好了。