Gọi phép dịch trái của một string \(t_1t_2t_3...t_{n-1}t_n\) là string \(t_2t_3...t_{n-1}t_nt_1\)

Gọi phép dịch phải của một string \(t_1t_2t_3...t_{n-1}t_n\) là string \(t_nt_1t_2t_3...t_{n-1}\)

Ví dụ: s = "4579" dịch trái là "5794", dịch phải là "9457"

Một string được gọi là good nếu phép dịch trái và phép dịch phải của nó bằng nhau.

Bạn được cho một string s chỉ bao gồm các kí tự từ 0 đến 9.

Hãy tính toán số lượng kí tự ít nhất cần xóa để làm cho string s trở thành good.

Input

• Dòng đầu tiên là số nguyên \(T (T \le 10)\) - là số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm một string \(s\) (\(s.size() \le 2*10^5\)).

Output

• Mỗi bộ dữ liệu in ra một số nguyên là số lượng ít nhất kí tự cần xóa để làm cho string s trở thành good.

Example

3
95831
100120013
252525252525

3
5
0