Let's call left cyclic shift of some string $t_1 t_2 t_3 \dots t_{n - 1} t_n$ as string $t_2 t_3 \dots t_{n - 1} t_n t_1$.

Analogically, let's call right cyclic shift of string $t$ as string $t_n t_1 t_2 t_3 \dots t_{n - 1}$.

Let's say string $t$ is good if its left cyclic shift is equal to its right cyclic shift.

You are given string $s$ which consists of digits 0–9.

What is the minimum number of characters you need to erase from $s$ to make it good?


-----Input-----

The first line contains single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Next $t$ lines contains test cases — one per line. The first and only line of each test case contains string $s$ ($2 \le |s| \le 2 \cdot 10^5$). Each character $s_i$ is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the minimum number of characters you need to erase from $s$ to make it good.


-----Example-----
Input
3
95831
100120013
252525252525

Output
3
5
0



-----Note-----

In the first test case, you can erase any $3$ characters, for example, the $1$-st, the $3$-rd, and the $4$-th. You'll get string 51 and it is good.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good.

In the third test case, the given string $s$ is already good.

Difficulty: interview

Starter code:

Solutions:
def det(s, i, j):
    ans = 0
    curr = i
    for a in s:
        if a == curr:
            ans += 1
            if curr == i: curr = j
            else: curr = i

    if i == j: return ans
    return ans // 2 * 2

for t in range(int(input())):
    s = list(map(int, list(input())))
    ans = 0
    
    for i in range(10):
        for j in range(10):
            ans = max(ans, det(s, i, j))

    print(len(s)-ans)


for _ in range(int(input())):
    s=input()
    n=len(s)
    s=[int(s[i]) for i in range(n)]
    ans=2
    for a in range(10):
        for b in range(10):
            temp=0
            sign="a"
            for i in range(n):
                if sign=="a":
                    if s[i]==a:
                        temp+=1
                        sign="b"
                else:
                    if s[i]==b:
                        temp+=1
                        sign="a"
            if a==b:
                ans=max(ans,temp)
            else:
                temp-=temp%2
                ans=max(ans,temp)
    print(n-ans)


from collections import Counter

t = int(input())

for _ in range(t):
    s = input()
    best = len(s) - max(Counter(s).values())
    longest = [[0 for _ in range(10)] for _ in range(10)]
    for c in s:
        ci = int(c)
        for j in range(10):
            if longest[ci][j] % 2 == 0:
                longest[ci][j] += 1
            if longest[j][ci] % 2:
                longest[j][ci] += 1

    # print(longest)
    best = min(best, len(s) - max(longest[i][j] - (longest[i][j] % 2) for i in range(10) for j in range(10) if i != j))
    print(best)


import math
import sys
input = sys.stdin.readline

T = int(input())

for t in range(T):
    s = input()[:-1]

    answer = math.inf
    for n1 in range(10):
        sn1 = str(n1)
        for n2 in range(10):
            sn2 = str(n2)
            lookn1 = True
            current = 0
            for c in s:
                if c == sn1 and lookn1:
                    lookn1 = False
                    current += 1
                elif c == sn2 and not lookn1:
                    lookn1 = True
                    current += 1
            if current % 2 and n1 != n2:
                current -= 1

            answer = min(answer, len(s)-current)

    print(answer)