Cổng thông tin sinh viên của Đại học Công nghiệp Hà Nội vừa siết chặt chính sách bảo mật. Một mật khẩu được gọi là mạnh nếu thoả mãn đồng thời các điều kiện sau:

• có độ dài ít nhất ~8~ ký tự;
• có ít nhất một chữ cái thường (a đến z), ít nhất một chữ cái hoa (A đến Z) và ít nhất một chữ số (0 đến 9);
• có ít nhất một ký tự đặc biệt, tức là ký tự không phải chữ cái, không phải chữ số.

Với mỗi mật khẩu trong danh sách ~n~ mật khẩu, ban quản trị muốn gợi ý cách sửa ít tốn công nhất: chỉ thêm các ký tự tuỳ chọn vào vị trí bất kỳ, không xoá và không thay đổi ký tự đã có.

Yêu cầu

Với mỗi mật khẩu, hãy tính số ký tự ít nhất cần thêm vào để nó trở thành mật khẩu mạnh.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~n~;
• Mỗi dòng trong ~n~ dòng tiếp theo chứa một mật khẩu: xâu khác rỗng, không có dấu cách, gồm các ký tự ASCII có mã từ ~33~ đến ~126~ (chữ cái, chữ số, ký hiệu như !, @, #, _, /, [, }).

Kết quả ra

Ghi ra ~n~ dòng: dòng thứ ~i~ ghi số ký tự ít nhất cần thêm vào mật khẩu thứ ~i~ (ghi ~0~ nếu đã mạnh).

Ràng buộc

~1 \le n \le 1000~; mỗi mật khẩu có độ dài từ ~1~ đến ~100~.

• Subtask 1 (30% số điểm – test 01–06): mọi mật khẩu có độ dài ít nhất ~8~;
• Subtask 2 (30% số điểm – test 07–12): mọi mật khẩu chỉ gồm chữ cái thường;
• Subtask 3 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

5
haui2026
Ab1#
CNTT@HaUI2026
abc
K17-PM!

Kết quả ra mẫu 1

2
4
0
5
1

Giải thích

haui2026 đã đủ dài, còn thiếu chữ hoa và ký tự đặc biệt: thêm ~2~ ký tự. Ab1# có đủ bốn loại ký tự nhưng mới dài ~4~: thêm ~4~ ký tự bất kỳ. CNTT@HaUI2026 đã mạnh. abc phải thêm ~5~ ký tự cho đủ dài, trong đó chọn một chữ hoa, một chữ số, một ký tự đặc biệt. K17-PM! dài ~7~, chỉ thiếu chữ thường: thêm một chữ thường.