와일드카드 괄호 문자열

‘(’, ‘)’로 이루어진 문자열이 올바른 괄호 문자열이라는 것은 다음을 의미합니다.

• $S$가 빈 문자열이면, $S$는 올바른 괄호 문자열입니다.
• $S$가 올바른 괄호 문자열이면, $S$의 앞뒤에 각각 ‘(’와 ‘)’를 붙여 만든 문자열 “($S$)” 는 올바른 괄호 문자열입니다.
• $S$와 $T$가 올바른 괄호 문자열이면, $S$와 $T$를 붙여 만든 문자열 “$ST$”는 올바른 괄호 문자열입니다.
• 위 세 규칙을 통해 만들 수 없는 문자열은 올바른 괄호 문자열이 아닙니다.

예를 들어, “(())()”, “()()”은 올바른 괄호 문자열이고 “)(”, “())(”는 올바른 괄호문자열이 아닙니다.

문자열 $S$가 주어집니다. $S$는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 문자열입니다. ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’와 ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 있나요?

첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1 \le T \le 10\\,000)$

각 테스트케이스의 첫 줄에는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 길이가 $1$ 이상 $500\\,000$ 이하인 문자열 $S$가 주어집니다.

입력에서 주어진 문자열 $S$의 길이 합은 $500\\,000$을 넘지 않습니다.

각 테스트케이스마다 한 줄에 하나씩, ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’, ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 있다면 “YES”, 불가능하면 “NO”를 출력하세요.