Cho một xâu ký tự chỉ gồm các ký tự (, ), [, ], {, }. Hãy kiểm tra xem xâu đó có phải là biểu thức ngoặc hợp lệ hay không.

Một biểu thức ngoặc được gọi là hợp lệ khi:

• Mỗi ngoặc mở đều có đúng một ngoặc đóng tương ứng cùng loại.
• Các ngoặc được đóng mở theo đúng thứ tự.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ — số lượng bộ test ~(1 \le T \le 100)~.
• Mỗi trong $T$ dòng tiếp theo chứa một xâu ~S~ ~(1 \le |S| \le 10^5)~.

Dữ liệu ra

Với mỗi bộ test, in ra YES nếu xâu hợp lệ, ngược lại in ra NO.

Ví dụ

Input:

5
()[]{}
([{}])
(]
([)]
{[}

Output:

YES
YES
NO
NO
NO

Giới hạn

Gợi ý: Dùng Stack để lưu các ngoặc mở. Khi gặp ngoặc đóng, kiểm tra đỉnh Stack có khớp không.