In 2077, robots decided to get rid of balanced bracket sequences once and for all!

A bracket sequence is called balanced if it can be constructed by the following formal grammar.

The empty sequence $$$\varnothing$$$ is balanced.
If the bracket sequence $$$A$$$ is balanced, then $$$\mathtt{(}A\mathtt{)}$$$ is also balanced.
If the bracket sequences $$$A$$$ and $$$B$$$ are balanced, then the concatenated sequence $$$A B$$$ is also balanced.

You are the head of the department for combating balanced bracket sequences, and your main task is to determine which brackets you can destroy and which you cannot.

You are given a balanced bracket sequence represented by a string $$$s$$$, consisting of the characters ( and ). Since the robots' capabilities are not limitless, they can remove exactly one opening bracket and exactly one closing bracket from the string.

Your task is to determine whether the robots can delete such two brackets so that the string $$$s$$$ is no longer a balanced bracket sequence.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of a single string $$$s$$$ ($$$2 \leq |s| \leq 2 \cdot 10^5$$$) — a sequence of the characters ( and ).

It is guaranteed that $$$s$$$ is a balanced bracket sequence.

It is also guaranteed that the sum of $$$|s|$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output "YES" if the robots can make the string stop being a balanced bracket sequence, and "NO" otherwise.

You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Note

In the first test case, it can be shown that the robots will not be able to break the correct bracket sequence.

In the second test case, one of the options for removing brackets is as follows:

$$$\texttt{(())}\color{red}{\texttt{(}}\texttt{)(}\color{red}{\texttt{)}} \rightarrow \texttt{(()))(}$$$, which is not a correct bracket sequence.

In the fourth test case, one of the options for removal is as follows:

$$$\texttt{(}\color{red}{\texttt{(}}\texttt{))((}\color{red}{\texttt{)}}\texttt{)}\rightarrow \texttt{())(()}$$$, which is not a correct bracket sequence.

Idx	Name	Rating
A	Fashionable Array	800
B	Down with Brackets	900
C	Racing	1400
D	Fewer Batteries	1700
E	Melody	2300
F	Faculty	2400

Codeforces Round 1026 (Div. 2)