Let's call left cyclic shift of some string t_1 t_2 t_3 ... t_{n - 1} t_n as string t_2 t_3 ... 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 ... 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 ≤ t ≤ 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 ≤ |s| ≤ 2 ⋅ 10^5). Each character s_i is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed 2 ⋅ 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.
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# ------------------- fast io --------------------

#try to delete as few as possible to make it 2-periodic
#either all the same or alternating with even length
testcases=int(input())

for j in range(testcases):
    vals=[int(k) for k in input()]
    dict1={}
    dict2={}
    for s in range(len(vals)):
        if not(vals[s] in dict1):
            dict1[vals[s]]=[s]
            dict2[vals[s]]=1
        else:
            if dict1[vals[s]][-1]+1==s:
                dict1[vals[s]][-1]=s
            else:
                dict1[vals[s]].append(s)
            dict2[vals[s]]+=1
    move1=len(vals)-max(dict2.values())
    maxmove=len(vals)
    #theres only 9
    for s in range(10):
        if s in dict1:
            for b in dict1.keys():
                if b==s:
                    continue
                else:
                    p1=0
                    p2=0
                    length=0
                    checker=0
                    while p1<len(dict1[s]) or p2<len(dict1[b]):
                        if p1==p2==0:
                            if dict1[s][p1]<=dict1[b][p2]:
                                p1+=1
                                checker=0
                            else:
                                p2+=1
                                checker=1
                            length+=1
                        else:
                            if p1<len(dict1[s]) and p2<len(dict1[b]):
                                if checker==0:
                                    if dict1[b][p2]>dict1[s][p1-1]:
                                        length+=1
                                        checker=1
                                    p2+=1
                                else:
                                    if dict1[s][p1]>dict1[b][p2-1]:
                                        length+=1
                                        checker=0
                                    p1+=1
                            else:
                                #1 of them already maxed out
                                if checker==0:
                                    if p2<len(dict1[b]):
                                        if dict1[b][p2]>dict1[s][p1-1]:
                                            length+=1
                                            break
                                        p2+=1
                                    else:
                                        break
                                else:
                                    if p1<len(dict1[s]):
                                        if dict1[s][p1]>dict1[b][p2-1]:
                                            length+=1
                                            break
                                        p1+=1
                                    else:
                                        break
                    if len(vals)-(length-length%2)<maxmove:
                        maxmove=len(vals)-(length-length%2)
    print(min(maxmove,move1))