B. Party Monster

Yousef has given you a sequence 𝑠

 of length 𝑛

 consisting only of characters '(

' and ')

'. You are allowed to perform the following operation at most once:

• Choose a substring
• ∗
•  of 𝑠
•  and remove it. Then, you may reinsert the removed characters back into the remaining string one by one. Each character can be placed at any arbitrary position, independently of the others.

Yousef wants you to determine whether it is possible to obtain a regular bracket sequence

†

 after performing the operation at most once.

∗

A substring is a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position 3

 and ends in position 6

), but "aa" or "d" aren't substrings of this string. So the substring of the string 𝑠

 from position 𝑙

 to position 𝑟

 is 𝑠[𝑙,𝑟]=𝑠

𝑙

𝑠

𝑙+1

…𝑠

𝑟

.

†

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters 1

 and +

 between the original characters of the sequence. For example:

• bracket sequences ()()
•  and (())
•  are regular (the resulting expressions are: (𝟷)+(𝟷)
•  and ((𝟷+𝟷)+𝟷)
• );
• bracket sequences )(
• , (
•  and )
•  are not.

Input

The first line contains an integer 𝑡

 (1≤𝑡≤10

4

) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer 𝑛

 (1≤𝑛≤2⋅10

5

) — the length of the string 𝑠

.

The second line of each test case contains a sequence 𝑠

 of length 𝑛

 consisting only of characters '(

' and ')

'.

It is guaranteed that the sum of 𝑛

 over all test cases does not exceed 2⋅10

5

.

Output

For each test case, output "YES" if the sequence can be made regular, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example

Input

Copy

6
2
()
2
)(
3
(((
6
())(()
4
(()(
5
)()()

Output

Copy

YES
YES
NO
YES
NO
NO

Note

In the first test case, the string 𝑠

 is already a regular bracket sequence, therefore the answer is "YES".

In the second test case, we can remove the substring 𝑠[2,2]=(

 and reinsert it at the beginning of the string, making 𝑠=()

, therefore the answer is "YES".

In the third test case, there is no way to do the operation and get a regular bracket sequence, so the answer is "NO".

In the fourth test case, we can choose the substring 𝑠[3,4]=)(

, remove it, then reinsert the characters as follows:

())(()→()()→(()())

Therefore we have made a regular bracket sequence, and the answer is "YES".