Problem Description

Xiao Lan is a loyal user of Lanqiao Cloud Class. He has registered $n$ accounts on the platform, and the password of each account is a string consisting only of uppercase and lowercase letters and digits. Recently, in order to improve account security, Lanqiao Cloud Class requires all users to change their passwords to meet a new security policy: the password must contain at least one lowercase letter, one uppercase letter, and one digit.

Xiao Lan does not want to change his commonly used passwords too much, because he is already very used to them. So, he plans to do some simple replacement operations to modify the password, keeping the original structure as much as possible. Specifically, in each operation, he can replace between the uppercase letter O, the lowercase letter o, and the digit 0. That is, one operation can be one of the following:

• Change one uppercase letter O into a lowercase letter o.
• Change one uppercase letter O into the digit 0.
• Change one lowercase letter o into an uppercase letter O.
• Change one lowercase letter o into the digit 0.
• Change one digit 0 into an uppercase letter O.
• Change one digit 0 into a lowercase letter o.

Now, Xiao Lan wants you to help him compute, for each account password, the minimum number of replacement operations needed to meet the new security policy. If it is impossible to meet the new policy no matter how you replace, output $-1$, meaning the password cannot be made valid through these replacements.

Input Format

The first line contains an integer $n$, representing the number of Xiao Lan's accounts.

The next $n$ lines each contain a string $S$ consisting only of uppercase and lowercase English letters and digits, representing a password.

Output Format

Output $n$ lines. Each line contains an integer representing the minimum number of operations required to modify the corresponding password. If it is impossible to meet the new policy, output $-1$.

3
zxcvbn12
oooooooo
123abcABC

-1
2
0

Hint

Constraints and Notes for Test Cases

For all test cases, $1 \le n \le 100$, $8 \le |S| \le 16$, where $|S|$ denotes the length of the string $S$.

Translated by ChatGPT 5