Description

A string consisting only of uppercase and lowercase English letters is called a "Five-Letter Deity" if and only if the total length of the string is $5$ or the number of uppercase letters is $5$.

mxzhn gives you a non-empty string $S$ (containing only uppercase and lowercase English letters). You need to transform this string into a "Five-Letter Deity" using any number of the following three operations:

1. If the string is non-empty, delete any one character.
2. Modify any one character to an uppercase or lowercase letter.
3. Append a lowercase letter to the end of the string.

Find the minimum number of operations required.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases. For each test case:

• One line, a non-empty string $S$. It is guaranteed that $S$ contains only uppercase and lowercase English letters.

Output Format

For each test case, output one line containing an integer, which is the corresponding minimum number of operations.

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

Hint

【Sample Explanation #1】

For the three strings:

1. mxzhn already satisfies the requirement without any changes.
2. tymxzhn can be transformed into mxzhn by deleting the first two characters.
3. vegetableking can be changed to VeGeTaBleKing within five operations.

It can be proved that the number of operations is minimal for each. Note that there may be multiple ways to achieve the same result with the same number of operations.

【Data Range】

Let $\lvert S \rvert$ denote the length of string $S$.

The test cases are not equally weighted. See the score column for details.

For all test cases, $1\le \lvert S \rvert \le 20$, $1\le T\le 10^4$, and the string contains only uppercase and lowercase English letters.

Translated by DeepSeek V3.1