← 返回题目列表

Codeforces · 1389/C

C. 好弦

中文机器翻译题面 查看原题

让我们将某个字符串 $$$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$$$ 已经很好了。