310357: CF1821C. Tear It Apart

C. Tear It Aparttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$, consisting of lowercase Latin letters.

In one operation, you can select several (one or more) positions in it such that no two selected positions are adjacent to each other. Then you remove the letters on the selected positions from the string. The resulting parts are concatenated without changing their order.

What is the smallest number of operations required to make all the letters in $s$ the same?

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The only line of each testcase contains a string $s$, consisting of lowercase Latin letters. Its length is from $1$ to $2 \cdot 10^5$.

The total length of the strings over all testcases doesn't exceed $2 \cdot 10^5$.

Output

For each testcase, print a single integer — the smallest number of operations required to make all the letters in the given string $s$ the same.

ExampleInput

5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul

Output

1
3
0
2
4

Note

In the first testcase, you can select positions $2, 4$ and $6$ and remove the corresponding letters 'b', 'c' and 'b'.

In the third testcase, the letters in the string are already the same, so you don't have to make any operations.

In the fourth testcase, one of the possible solutions in $2$ operations is the following. You can select positions $1, 4, 6$ first. The string becomes "bce". Then select positions $1$ and $3$. The string becomes "c". All letters in it are the same, since it's just one letter.

题目大意：给定一个由小写拉丁字母组成的字符串 s。你可以选择字符串中的几个（一个或多个）位置，使得选中的位置不相邻，然后移除这些位置上的字母，剩余的部分按原顺序拼接。求使字符串 s 中所有字母都相同所需的最小操作次数。

输入输出数据格式：

输入：
- 第一行包含一个整数 t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例占一行，包含一个字符串 s，由小写拉丁字母组成，长度在 1 到 2×10^5 之间。
- 所有测试用例的字符串总长度不超过 2×10^5。

输出：
- 对于每个测试用例，输出一个整数，表示使给定字符串 s 中所有字母都相同所需的最小操作次数。

示例：

输入：
```
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul
```

输出：
```
1
3
0
2
4
```

注意：
- 在第一个测试用例中，可以选择位置 2、4 和 6，并移除相应的字母 'b'、'c' 和 'b'。
- 在第三个测试用例中，字符串中的字母已经全部相同，因此不需要进行任何操作。
- 在第四个测试用例中，一种可能的解决方案需要 2 次操作。首先选择位置 1、4 和 6，字符串变为 "bce"。然后选择位置 1 和 3，字符串变为 "c"。由于只剩下一个字母，所以所有字母都相同。题目大意：给定一个由小写拉丁字母组成的字符串 s。你可以选择字符串中的几个（一个或多个）位置，使得选中的位置不相邻，然后移除这些位置上的字母，剩余的部分按原顺序拼接。求使字符串 s 中所有字母都相同所需的最小操作次数。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例占一行，包含一个字符串 s，由小写拉丁字母组成，长度在 1 到 2×10^5 之间。 - 所有测试用例的字符串总长度不超过 2×10^5。 输出： - 对于每个测试用例，输出一个整数，表示使给定字符串 s 中所有字母都相同所需的最小操作次数。 示例： 输入： ``` 5 abacaba codeforces oooooooo abcdef mewheniseearulhiiarul ``` 输出： ``` 1 3 0 2 4 ``` 注意： - 在第一个测试用例中，可以选择位置 2、4 和 6，并移除相应的字母 'b'、'c' 和 'b'。 - 在第三个测试用例中，字符串中的字母已经全部相同，因此不需要进行任何操作。 - 在第四个测试用例中，一种可能的解决方案需要 2 次操作。首先选择位置 1、4 和 6，字符串变为 "bce"。然后选择位置 1 和 3，字符串变为 "c"。由于只剩下一个字母，所以所有字母都相同。