Password check

Dublin City University wants to stop students and staff from using weak passwords. The security department asked you to write a program that checks whether a password meets every quality requirement set by the password guidelines council.

The requirements are as follows. A password is strong enough when it has all of these properties:

• At least one lowercase letter.
• At least one uppercase letter.
• At least one digit.
• At least one symbol from the set +_)(*&^%$#@!./,;{}.
• Length at least 12.

For example, Aa1_ meets the first four requirements but is shorter than 12 characters. Aa1234567890_ meets every requirement.

One input holds a batch of passwords to process.

The first line contains an integer $N$, the number of passwords to process.

Each password is given on two lines. The first line contains an integer $S$, the size of the password. The next line contains a sequence of $S$ characters, the password to check.

A password contains only the letters a to z (lowercase and uppercase), the digits 0 to 9, and the symbols +_)(*&^%$#@!./,;{}.

The size of a password is at most 30, and one input contains at most 100 passwords.

For each password, write a line with valid if the password meets the quality requirements, or invalid otherwise. Keep the order in which the passwords were given.