An engineer is designing a system and needs to create valid passwords for it. However, the passwords must follow specific rules to be considered valid. Each password the engineer proposes must be evaluated to ensure it is valid according to these rules.

Password Validation Rules:

1. An empty password is always valid.
2. If a valid password A exists, adding the same character X to both the beginning and the end of A creates a new valid password C.
3. If two passwords A and B are valid, their concatenations AB and BA are also valid.

The engineer proposed N passwords, each passwords consisting of only lowercase English characters, where the ith password is denoted passwords[i]. Determine if each password is valid or not. A valid password is denoted by 1 in the answer array while an invalid password is denoted by 0.