Một dãy ngoặc đúng là một xâu gồm các ký tự (, ), [, ], { và } định nghĩa như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng,
• Nếu A và B là hai dãy ngoặc đúng thì AB (xâu tạo thành bằng cách lấy xâu A nối vào trước xâu B) cũng là một dãy ngoặc đúng,
• Nếu A là một dãy ngoặc đúng thì (A), [A] và {A} cũng là những dãy ngoặc đúng.
  Những xâu không thành lập được theo quy tắc trên không phải là dãy ngoặc đúng.

Ví dụ {[()()[]()]}() là một dãy ngoặc đúng nhưng [(]) và }}}{{{ không phải là những dãy ngoặc đúng.

Input

Dữ liệu nhập từ tệp DAYNGOAC.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(n (n\leq 10)\)
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự có độ dài không vượt quá \(10^6\) và chỉ chứa các ký tự (, ), [, ], { và }.

Output

Dữ liệu in ra tệp DAYNGOAC.OUT theo cấu trúc như sau:
- Ghi \(n\) dòng, mỗi dòng ghi YES/NO tương ứng với xâu tương ứng có phải là dãy ngoặc đúng hay không.

4
{[()()[]()]}()
[(])
([{}]){[()]}
{{{}}

YES
NO
YES
NO