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.
import time,math as mt,bisect,sys
from sys import stdin,stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi=3.14159265358979323846264338327950
def II(): # to take integer input
    return int(stdin.readline())
def IO(): # to take string input
    return stdin.readline()
def IP(): # to take tuple as input
    return map(int,stdin.readline().split())
def L(): # to take list as input
    return list(map(int,stdin.readline().split()))
def P(x): # to print integer,list,string etc..
    return stdout.write(str(x)+"\n")
def PI(x,y): # to print tuple separatedly
    return stdout.write(str(x)+" "+str(y)+"\n")
def lcm(a,b): # to calculate lcm
    return (a*b)//gcd(a,b)
def gcd(a,b): # to calculate gcd
    if a==0:
        return b
    elif b==0:
        return a
    if a>b:
        return gcd(a%b,b)
    else:
        return gcd(a,b%a)
def readTree(): # to read tree
    v=int(input())
    adj=[set() for i in range(v+1)]
    for i in range(v-1):
        u1,u2=In()
        adj[u1].add(u2)
        adj[u2].add(u1)
    return adj,v
def bfs(adj,v): # a schema of bfs
    visited=[False]*(v+1)
    q=deque()
    while q:
        pass
def sieve():
    li=[True]*1000001
    li[0],li[1]=False,False
    for i in range(2,len(li),1):
        if li[i]==True:
            for j in range(i*i,len(li),i):
                li[j]=False
    prime=[]
    for i in range(1000001):
        if li[i]==True:
            prime.append(i)
    return prime
def setBit(n):
    count=0
    while n!=0:
        n=n&(n-1)
        count+=1
    return count
mx=10**7
spf=[mx]*(mx+1)
def SPF():
    spf[1]=1
    for i in range(2,mx+1):
        if spf[i]==mx:
            spf[i]=i
            for j in range(i*i,mx+1,i):
                if i<spf[j]:
                    spf[j]=i
    return
#####################################################################################
mod=10**9+7
def solve(i):
    s=input()
    n=len(s)
    ans=1e7
    for i in range(10):
        for j in range(10):
            findi,findj=True,False
            count=0
            i,j=str(i),str(j)
            for k in range(n):
                if i==j and s[k]==i:
                    count+=1
                else:
                    if (findi==True) and (s[k]==i):
                        findi=False
                        count+=1
                        findj=True
                    if findj==True and s[k]==j:
                        findj=False
                        count+=1
                        findi=True
            if i==j:
                ans=min(ans,n-count)
            else:
                if count%2==0:
                    ans=min(ans,n-count)
                else:
                    ans=min(ans,n-(count-1))
    P(ans)
    return


t=II()
for i in range(t):
    solve(i)

    #######
   #
  #
 #######   #     #  # ####   # #     #
       #  # #   #  # #   #  # # #   #
      #  ####  #  # ####   ####  # #
######  #   # #### #    # #   #   #