Thỏ thích làm các bài tập về xử lý chuỗi. Thỏ định nghĩa rằng một chuỗi được gọi là tốt
là một chuỗi mà tất cả các kí tự \(alphabet\) trong đó đều là kí tự hoa hoặc là kí tự thường

Ví dụ :

• ABCDEF là một chuỗi tốt

• xyabx@# là một chuỗi tốt

• Xy3z5A là một chuỗi xấu

Trong khi đọc tài liệu, Thỏ cảm thấy có rất nhiều chuỗi xấu xuất hiện và Thỏ muốn chuyển tất cả
các chuỗi xấu này thành chuỗi tốt với số lượng thao tác là ít nhất có thể.

Trong một thao tác, Thỏ chỉ có thể thay đổi MỘT kí tự trong xâu S thành một kí tự bất kì nào đó.

Bạn hãy giúp Thỏ tìm số lượng thao tác nhỏ nhất có thể để chuyển chuỗi xấu thành chuỗi tốt nhé.

Input

• Dòng đầu tiên là số \(T\) số lượng test case \((1 \leq T \leq 10)\).

• \(T\) dòng tiếp theo , mỗi dòng chứa một xâu \(S\) là chuỗi cần phải chuyển \((1 \leq Len(S) \leq 100)\).

Output

• Tương ứng với mỗi chuỗi \(S\), in ra số lượng thao tác để chuyển chuỗi \(S\) thành chuỗi tốt, nếu trong chuỗi
  không có kí tự alphabet nào, in ra Invalid Input.

Example

3
abcEfg
!@6#2
123A

1
Invalid Input   
0