Cho xâu ~S~ có độ dài ~N~ chỉ bao gồm các ký tự ’(’, ’)’ và ’*’.

Ta định nghĩa một dãy ngoặc đúng như sau:

• Nếu dãy không có ký tự nào thì được gọi là một dãy ngoặc đúng.
• Nếu A là một dãy ngoặc đúng thì (A) cũng là một dãy ngoặc đúng.
• Nếu A và B là các dãy ngoặc đúng thì AB là một dãy ngoặc đúng.

Hãy kiểm tra xem có tồn tại một cách nào thay thế các ký tự ’*’ của xâu ~S~ thành ký tự ’(’ hoặc’)’ sao cho xâu ~S~ trở thành một dãy ngoặc đúng hay không.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ tương ứng với số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một xâu S chỉ bao gồm các ký tự ’(’, ’)’ và ’*’ có độ dài không quá ~N~ (chi tiết giới hạn của ~N~ xem ở phần giới hạn).

Giới hạn:

• Subtask 1 (20%): ~1 ≤ N ≤ 100~, xâu ~S~ không chứa ký tự ’*’.
• Subtask 2 (60%): ~1 ≤ N ≤ 1000~.
• Subtask 3 (20%): ~1 ≤ N ≤ 10^4~

Output

In ra T dòng, mỗi dòng in ra "YES" hoặc "NO" (không bao gồm dấu ngoặc kép) tương ứng với có hay không có cách thay thế các ký tự ’*’ thành ký tự ’(’ hoặc ’)’ để xâu ~S~ trở thànhmột dãy ngoặc đúng.

Sample

Input #1

6
(())()
**
(*()
(**)
(*)**(
*****

Output #1

YES
YES
YES
YES
NO
NO

Hint

• Trong test ví dụ thứ nhất, (())() đã là dãy ngoặc đúng.
• Trong test ví dụ thứ hai, có thể thay thế ** thành ().
• Trong test ví dụ thứ ba, có thể thay thế (*() thành ()().
• Trong test ví dụ thứ tư, có thể thay thế (**) thành (()).
• Trong test ví dụ thứ năm và thứ sáu, không có cách nào để chuyển xâu thành dãy ngoặc đúng.

Problem source: Kc97ble - Free Contest