给你一个字符串 $$$s$$$,由小写拉丁字母组成。
在一项操作中,您可以选择其中的多个(一个或多个)位置,使得两个选定位置不会彼此相邻。然后从字符串中删除选定位置上的字母。将所得部分连接起来而不改变其顺序。
最少需要多少次运算才能使 $$$s$$$ 中的所有字母都相同?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个字符串 $$$s$$$,由小写拉丁字母组成。它的长度是从 $$$1$$$ 到 $$$2 \cdot 10^5$$$。
所有测试用例的字符串总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 使给定字符串 $$$s$$$ 中的所有字母相同所需的最少操作数。
示例
输入 #1
5 abacaba codeforces oooooooo abcdef mewheniseearulhiiarul
输出 #1
1 3 0 2 4
注意
在第一个测试用例中,您可以选择位置 $$$2、4$$$ 和 $$$6$$$ 并删除相应的字母 'b'、'c' 和 'b'。
在第三个测试用例中,字符串中的字母已经相同,因此您不必进行任何操作。
在第四个测试用例中,$$$2$$$ 操作中可能的解决方案之一如下。您可以先选择位置 $$$1, 4, 6$$$。该字符串变为“bce”。然后选择位置$$$1$$$ 和$$$3$$$。该字符串变为“c”。其中的所有字母都是相同的,因为它只是一个字母。