Prangan Found a parentheses sequence while walking along the road of Comilla University. He wants to make the sequence as a valid parentheses sequence, because he learned it from his room-mate Mozahid last night. Prangan made the sequence valid very easily. But Mozahid now made it a bit tricky for Prangan. He told Prangan to make a substring of the sequence valid. He will give the left and the right position (L and R) of that substring. And he will ask it Q times.

As Prangan is not good at Programming like you, he is seeking help from door to door.

Please Help him.

Note to mention that: a valid parentheses sequence is a parentheses sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the characters of the string. For example, parentheses sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

Input

The first line contains positive integer t (1 ≤ t ≤ 100) — the number of test cases.

Each test case contains a positive integer N (1 <= N <= 100000), which is the length of parentheses sequence Prangan Found.

Next Line contains a non-empty string S consisting of only characters '(', ')'.

Next Line contains a positive integer Q (1 <= Q <= 100000) denotes the number of queries.

In each query there will be two positive integer L and R (1 <= L <= R <= N). Summation of all N will not be greater than 500000.

Output

For each query you have to print "YES" if it is possible to make the sequence valid rearranging parentheses in between position L to R.

See the sample output below for better understanding.

Example

Input:
etc.

Output:
etc.