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?

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$.

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