Một dấu ngoặc bao gồm những ký tự như sau: (, ), {, }, [, or ].

Một cặp ngoặc đúng bao gồm (), {}, []. Còn lại, những cặp ngoặc như ((, (}, [},... đều không phải là cặp ngoặc đúng.

Ta định nghĩa một chuỗi ngoặc đúng như sau:

1. Là một chuỗi rỗng.
2. Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm ở giữa một cặp ngoặc đúng. (VD: "[{}]" là đúng thì "(+[{}]+)" sẽ đúng).
3. Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm bên cạnh một chuỗi ngoặc đúng. (VD: "{[]}" là đúng thì "{[]}+[()]" sẽ đúng).

Đề bài cho bạn \(N\) chuỗi ngoặc. Nếu chuỗi thứ \(i\) là chuỗi ngoặc đúng, in ra YES, ngược lại in ra NO.

Input

• Dòng đầu tiên chứa số nguyên \(N\) là số truy vấn \((1 \leq N \leq 1000)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi ký tự \(S_i\), chỉ bao gồm các dấu ngoặc. $(1 \leq $ Độ dài \(S_i \leq 1000)\)

Output

• \(N\) dòng, dòng thứ \(i\) in ra YES hoặc NO tương ứng với nếu chuỗi \(S_i\) là chuỗi ngoặc đúng hoặc không đúng.

Example

3
{[()]}
{[(])}
{{[[(())]]}}

YES
NO
YES