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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main
{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}

public static void main(String[] args)
{
   FastReader in = new FastReader();
   int test=in.nextInt();
   
   while(test-->0)
   {
       String s=in.next();
       int n=s.length();
       
       int freq[]=new int[10];
       
       for(int i=0;i<n;i++)
       {
           freq[s.charAt(i)-'0']++;
           
       }
       int max=Integer.MIN_VALUE;
       for(int i=0;i<=9;i++)
           max=Math.max(max,freq[i]);
       
       //System.out.println(max);
       for(int i=0;i<=9;i++)
       {
           
           for(int j=0;j<=9;j++)
           {
               int len=0,cur=i;
               for(int k=0;k<n;k++)
               {
                   char ch=s.charAt(k);
                   if(ch-'0'==cur){
                       len++;
                   if(cur==i)
                       cur=j;
                   else
                       cur=i;
                   }
               }
               len-=len%2;
              // System.out.println(i+" "+j+" "+ce+" "+co);
               max=Math.max(max,len);
           }
       }       
       System.out.println(n-max);
   }
}
}