A company's security team has asked employees to change their password for all the applications$/$software they are using each quarter for security reasons.

You are asked to create software that takes employee input as a list of passwords and checks if each password is strong or not. If a password is strong, the

software shows 'true'. If a password is not strong it shows 'false'.

A password is considered strong if the below conditions are satisfied:

It has at least $8$ characters.

It concains at least one lowercase letter.

It concains at least one uppercase letter.

It contains at least one digit.

It does not contain $2$ of the same characters in adjacent positions $($i$.$e$.$ "aab" violates this condition, but "aba" does not$).$

Write an algorithm to print $\text{'}$ue$\text{'}$ for each strong password and 'false' for each password that is not strong, from the given list of passwords.

Input

The first line of input consists of an integer$-$ password$\_$size, representing the number of applications$/$software that are being used by the employee $($N$).$

The next line consists of $N$ space$-$separated string representing the passwords for the applications$/$software$.$

Output

Print $N$ space$-$separated strings consisting of 'true' if the password is strong and 'false' if it is not strong.

Example

Input:

$4$

paSu$121$i pasWord$8476$# @$996$ystA$4$ pA$$

Outpuc

true true false false

Explanation:

$"$pA$5$s$")$ are not strong passwords, as $"$G$96$ystA$4"$ contains only $7$ characters and $"$pA$$5"$ doesn't contain any digits and only has $4$ characters.