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.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        final Scanner input = new Scanner(System.in);
        int totalCases = input.nextInt();

        while (totalCases-- > 0) {
            final String string = input.next();
            int[] characterOccurrence = new int[10];
            int maximumOccurrence = 0;
            int finalLength = 0;

            for (char firstCharacter = '0'; firstCharacter <= '9'; firstCharacter++) {
                for (char secondCharacter = '0'; secondCharacter <= '9'; secondCharacter++) {
                    boolean first = true;
                    int length = 0;

                    for (int index = 0; index < string.length(); index++) {
                        char character = string.charAt(index);

                        if (firstCharacter == '0' && secondCharacter == '0') {
                            maximumOccurrence = Math.max(maximumOccurrence, ++characterOccurrence[character - '0']);
                        }

                        if (first && character == firstCharacter) {
                            first = false;
                        } else if (!first && character == secondCharacter) {
                            first = true;
                            length++;
                        }
                    }

                    finalLength = Math.max(finalLength, 2 * length);
                }
            }

            finalLength = Math.max(finalLength, maximumOccurrence);
            System.out.println(string.length() - finalLength);
        }
    }
    /*
    public static void main(String[] args) {
        final Scanner input = new Scanner(System.in);
        int totalCases = input.nextInt();

        while (totalCases-- > 0) {
            int[] array = new int[input.nextInt()];
            int totalMismatches = 0;
            int firstMismatch = -1;
            int lastMismatch = -1;

            for (int index = 0; index < array.length; index++) {
                array[index] = input.nextInt();

                if (array[index] != index + 1) {
                    totalMismatches++;
                    firstMismatch = firstMismatch == -1 ? index : firstMismatch;
                    lastMismatch = Math.max(lastMismatch, index);
                }
            }

            int result = 2;
            if (totalMismatches == 0) {
                result = 0;
            } else if (totalMismatches == lastMismatch - firstMismatch + 1) {
                result = 1;
            }

            System.out.println(result);
        }
    }

    public static void main(final String[] args) {
        final Scanner input = new Scanner(System.in);
        final int requiredLength = input.nextInt();

        System.out.println(recurse(requiredLength, true));
    }
    static long recurse(final int lengthRemaining, final boolean topVertex) {
        System.out.println(lengthRemaining + " " + topVertex);
        if (topVertex) {
            if (lengthRemaining == 0) {
                return 1;
            }

            return (3 * recurse(lengthRemaining - 1, false)) % 1000000007;
        } else {
            if (lengthRemaining == 0) {
                return 0;
            }

            return (recurse(lengthRemaining - 1, true) +
                    2 * recurse(lengthRemaining - 1, false)) % 1000000007;
        }
    }

     */

    /*
    public static int maxProfit(final int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        final int[] array = new int[prices.length];
        array[0] = 0;

        for (int index = 1; index < prices.length; index++) {
            array[index] = prices[index] - prices[index - 1];
        }

        int currentBest = 0;
        int result = 0;

        for (int element: array) {
            currentBest = Math.max(element, currentBest + element);
            result = Math.max(result, currentBest);
        }

        return result;
    }

    public int xorOperation(int n, int start) {
        int xor = 0;

        for (int index = 0; index < n; index++) {
            xor ^= start + 2 * index;
        }

        return xor;
    }

    public boolean stoneGame(int[] piles) {
        boolean alex = true;
        int sum = 0;
        int leftIndex = 0;
        int rightIndex = piles.length - 1;

        while (leftIndex < rightIndex) {
            if (alex) {
                sum += Math.max(piles[leftIndex], piles[rightIndex]);
            } else {
                sum -= Math.max(piles[leftIndex], piles[rightIndex]);
            }

            if (piles[leftIndex] < piles[rightIndex]) {
                leftIndex++;
            } else {
                rightIndex--;
            }

            alex = !alex;
        }

        return sum > 0;
    }

    public void deleteNode(ListNode node) {
        ListNode previous = null;

        while (node.next != null) {
            node.val = node.next.val;
            previous = node;
            node = node.next;
        }

        if (previous != null) {
            previous.next = null;
        }
    }

    public void solve(char[][] board) {
        for (int row = 0; row < board.length; row++) {
            for (int column = 0; column < board[0].length; column++) {
                if ()
            }
        }
    }

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        } else if (root.val == val) {
            return root;
        }

        TreeNode resultOne = searchBST(root.left, val);
        TreeNode resultTwo = searchBST(root.right, val);

        return resultOne == null ? resultTwo : resultOne;
    }

    public static int sumNumbers(TreeNode root) {
        return recurse(root, 0);
    }

    public static int recurse(final TreeNode node, int multiplier) {
        if (node == null) {
            return 0;
        }

        multiplier = multiplier * 10 + node.val;

        if (node.left == null && node.right == null) {
            return multiplier;
        }

        return recurse(node.left, multiplier) + recurse(node.right, multiplier);
    }

    public static int findDuplicate(final int[] nums) {
        final HashSet<Integer> elementsSeen = new HashSet<>();

        for (int element: nums) {
            if (elementsSeen.contains(element)) {
                return element;
            }

            elementsSeen.add(element);
        }

        return -1;
    }

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }


    public static int singleNumber(final int[] nums) {
        HashMap<Integer, Integer> counter = new HashMap<>();

        for (int element: nums) {
            counter.put(element, counter.getOrDefault(element, 0) + 1);
        }

        for (int element: counter.keySet()) {
            if (counter.get(element) == 1) {
                return element;
            }
        }

        return -1;
    }

    public static int uniquePaths(int m, int n) {
        HashMap<String, Integer> dp = new HashMap<>();
        return recurse(m, n, 1, 1, dp);
    }

    public static int recurse(final int rBound, final int cBound, final int row, final int column, final HashMap<String, Integer> dp) {
        if (row > rBound || column > cBound) {
            return 0;
        } else if (row == rBound && column == cBound) {
            return 1;
        } else if (dp.containsKey(row + " " + column)) {
            return dp.get(row + " " + column);
        }

        int resultOne = recurse(rBound, cBound, row + 1, column, dp);
        int resultTwo = recurse(rBound, cBound, row, column + 1, dp);

        dp.put((row + 1) + " " + column, resultOne);
        dp.put(row + " " + (column + 1), resultTwo);

        return resultOne + resultTwo;
    }

    public static List<String> findWords(final char[][] board, final String[] words) {
        final HashMap<Character, LinkedList<int[]>> location = new HashMap<>();
        final List<String> result = new LinkedList<>();

        for (int row = 0; row < board.length; row++) {
            for (int column = 0; column < board[0].length; column++) {
                char character = board[row][column];

                if (!location.containsKey(character)) {
                    location.put(character, new LinkedList<>());
                }

                location.get(character).add(new int[] {row, column});
            }
        }

        outer: for (String word: words) {
            final char character = word.charAt(0);

            if (location.containsKey(character)) {
                for (int[] coordinate: location.get(character)) {
                    Stack<int[]> beingVisited = new Stack<>();
                    beingVisited.push(new int[] {coordinate[0], coordinate[1], 0});
                    HashSet<String> visited = new HashSet<>();
                    visited.add(coordinate[0] + " " + coordinate[1]);

                    while (!beingVisited.isEmpty()) {
                        int[] triplet = beingVisited.pop();
                        int row = triplet[0];
                        int column = triplet[1];
                        int index = triplet[2];

                        if (index >= word.length()) {
                            result.add(word);
                            continue outer;
                        } else if (row < board.length && row >= 0 && column < board[0].length && column >= 0 && board[row][column] == word.charAt(index)) {
                            visited.add(row + " " + column);

                            if (!visited.contains((row + 1) + " " + column)) {
                                beingVisited.push(new int[]{row + 1, column, index + 1});
                            }

                            if (!visited.contains((row - 1) + " " + column)) {
                                beingVisited.push(new int[]{row - 1, column, index + 1});
                            }

                            if (!visited.contains(row + " " + (column + 1))) {
                                beingVisited.push(new int[]{row, column + 1, index + 1});
                            }

                            if (!visited.contains(row + " " + (column - 1))) {
                                beingVisited.push(new int[]{row, column - 1, index + 1});
                            }
                        }
                    }
                }
            }
        }

        return result;
    }
    */
}