Algorithm

C. Move Brackets
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1374/C
input
standard input
output
standard output

You are given a bracket sequence s� of length n�, where n� is even (divisible by two). The string s� consists of n2�2 opening brackets '(' and n2�2 closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index i�, remove the i�-th character of s� and insert it before or after all remaining characters of s�).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from s�. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

  • "()" is regular bracket sequence;
  • if s� is regular bracket sequence then "(" + s� + ")" is regular bracket sequence;
  • if s� and t� are regular bracket sequences then s� + t� is regular bracket sequence.

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer t� independent test cases.

Input

The first line of the input contains one integer t� (1≤t≤20001≤�≤2000) — the number of test cases. Then t� test cases follow.

The first line of the test case contains one integer n� (2≤n≤502≤�≤50) — the length of s�. It is guaranteed that n� is even. The second line of the test case containg the string s� consisting of n2�2 opening and n2�2 closing brackets.

Output

For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from s�. It can be proved that the answer always exists under the given constraints.

Example
input
Copy
4
2
)(
4
()()
8
())()()(
10
)))((((())
output
Copy
1
0
1
3
Note

In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    string s;
    cin>>s;
    stack<char> st;
    int count = 0;
    for(auto i : s){
      if(i == ')' && !st.empty()){
        st.pop();
        continue;
      }
      if(i == ')' && st.empty()){
        count++;
        continue;
      }
      st.push(i);
    }
    cout<<count<<endl;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
2
)(
4
()()
8
())()()(
10
)))((((())

Output

x
–
+
cmd
1
0
1
3
Advertisements

Demonstration

Codeforcess solution 1374-C C. Move Brackets ,C++, Java, Js and Python,1374-C,Codeforcess solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+