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

• Xâu rỗng là một dãy ngoặc đúng.
• Nếu A là một dãy ngoặc đúng thì (A), [A], {A} là một dãy ngoặc đúng.
• Nếu A và B là hai dãy ngoặc đúng thì AB là một dãy ngoặc đúng.

Cho một xâu S. Hãy xác định S có là dãy ngoặc đúng hay không.

Dữ liệu vào

Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm một xâu S có độ dài không vượt quá 100000.

Dữ liệu ra

Với mỗi test, in YES nếu S là dãy ngoặc đúng, ngược lại in NO.

Ví dụ

2
[()]{}{[()()]()}
[(])

YES
NO