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

Vào từ file văn bản PARENTHESES.INP

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

Output

Ghi ra file văn bản PARENTHESES.OUT ứng với mỗi xâu trong file dữ liệu, ghi ra trên một dòng từ YES nếu xâu đó là dãy ngoặc đúng, ghi ra từ NO nếu xâu đó không phải dãy ngoặc đúng.

Example

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

YES
NO
YES
NO

Nguồn: Thầy Lê Minh Hoàng