You are given n string, each string Si consisting of parentheses '(', ')', '[' and ']'.
A string S is said to be *correct* if:
1. S is the empty string
2. A and B are correct, S = AB
3. A is correct, S = (A) or S = [A]
Judge each of n string is *correct* or not. If yes, print a line "Y". Otherwise, print a line "N".
The first line contains an integer n — the total number of string you have to judge it is correct or not.
Each of the following n lines contains a string Si.
Restrictions
For each string, output one line following problem description.
Please add a newline at the end of the output. (Beside the last case)