题目描述

定义一个仅含大小写英文字母的字符串是“五字神人”的，当且仅当这个字符串的总长度为 $5$ 或者大写字母的数量为 $5$。

mxzhn 给你一个非空字符串 $S$（仅含大小写英文字母），你要用若干次以下三种操作把这个字符串变成“五字神人”的：

1. 若字符串非空，则删去任意一个字符。
2. 修改任意一个字符变为大写字母或小写字母。
3. 在字符串末尾添加一个小写字母。

求最少操作数。

输入格式

本题输入包含多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 仅一行，一个非空字符串 $S$。保证仅含大小写英文字母。

输出格式

对于每组测试数据，输出一行，一个整数，表示对应的最少操作数。

3
mxzhn
tymxzhn
vegetableking

0
2
5

9
TYmxzhn
VeGeTaBleKing
YuanShenQiDong
DuDuDu
NotCleverSYL
JianYu
wwwwwza
Anemones
wmrqwq

2
0
1
1
0
1
2
3
1

提示

【样例解释 #1】

对于三个字符串：

1. mxzhn 无需变动即可满足要求。
2. tymxzhn 可以删去前两个字符，变为 mxzhn。
3. vegetableking 可以把字符串变为 VeGeTaBleKing，五步操作内可以达到。

可以证明它们的操作数都是最少的。注意，达到相同答案的操作方法未必唯一。

【数据范围】

记号 $\lvert S \rvert$ 表示字符串 $S$ 的长度。

本题各个测试点不等分，详见分值一栏。

测试点编号	$\lvert S \rvert \le$	特殊性质	分值
$1$		无	$24$
$2$	$10$	字符串只含大写字母	$10$
$3$
$4$		字符串只含小写字母	$29$
$5$	$20$	无	$27$

对于所有测试点，$1\le \lvert S \rvert \le 20$，$1\le T\le 10^4$，保证字符串只含大小写英文字母。