Valid Password Construction

Problem Statement

Valid Password Construction An engineer is designing a system and needs to decide which of the proposed passwords may actually be used. A password is a string of lowercase English letters, and it is called valid only when its validity follows from the three construction rules below. Password validation rules The empty password is always valid. If a password A is valid and X is any lowercase English letter, then the password C = X + A + X (the letter X added to both the beginning and the end of A ) is also valid. If passwords A and B are both valid, then their concatenations AB and BA are also valid. A password that cannot be built from these rules is invalid. The engineer proposes n passwords. For every proposed password passwords[i] , report 1 if it is valid and 0 if it is not. Input Format The first line contains a single integer n , the number of proposed passwords. Each of the next n lines contains one non-empty string passwords[i] . Output Format Print n lines. The i -th line must