E. What Does the Cow Say?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Oh, Moo, Moo, Moo, I speak that normally!
— Bessie the Cow

Bessie gives you a regular bracket sequence (RBS)$$$^{\text{∗}}$$$ of length $$$n$$$ and an integer $$$k$$$.

In one operation, you can do the following:

  • Choose an index $$$i$$$ ($$$1 \le i \lt n$$$) such that $$$s_i s_{i+1} = \mathtt{()}$$$.
  • Let $$$s'$$$ denote the string obtained after removing these two characters from $$$s$$$.
  • Set $$$s := \mathtt{(} + s' + \mathtt{)}$$$.

You may perform this operation at most $$$k$$$ times (possibly zero). It can be shown that $$$s$$$ remains an RBS after every such operation.

The score of an RBS is defined as the maximum number of consecutive opening brackets '$$$\texttt{(}$$$' in the string. For example, the score of the string "$$$\texttt{(())((())())}$$$" is $$$3$$$.

Your task is to find the maximum possible score you can obtain by performing at most $$$k$$$ operations on the given string.

$$$^{\text{∗}}$$$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 $$$\texttt{()()}$$$ and $$$\texttt{(())}$$$ are regular (the resulting expressions are: $$$\texttt{(1)+(1)}$$$ and $$$\texttt{((1+1)+1)}$$$);
  • bracket sequences $$$\texttt{)(}$$$, $$$\texttt{(}$$$ and $$$\texttt{)}$$$ are not.
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.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\le n \le 4 \cdot 10^5$$$, $$$0 \le k \le \frac{n}{2}$$$) — the length of the RBS and the maximum number of operations you may perform.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters '$$$\texttt{(}$$$' and '$$$\texttt{)}$$$' — the given RBS.

It is guaranteed that $$$s$$$ is a regular bracket sequence, and that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum score you can obtain by performing at most $$$k$$$ operations.

Example
Input
9
2 0
()
4 1
(())
6 2
()()()
8 1
()((()))
8 3
(()())()
12 4
((()())())()
16 1
()(((()((())))))
22 1
((((()()(())((()))))))
28 0
(((()(((())()((())))())))())
Output
1
2
3
4
4
6
6
6
4
Note

In the first test case, we cannot perform any operations. The maximum number of consecutive opening brackets is $$$1$$$.

In the third test case, we can choose index $$$i = 1$$$, performing the operation gives us $$$s = $$$ "$$$\texttt{(()())}$$$". Then, choosing index $$$i = 4$$$ gives us $$$s = $$$ "$$$\texttt{((()))}$$$". We used $$$2$$$ operations and got a score of $$$3$$$, which is the maximum possible score.

In the seventh test case, we can choose index $$$i = 6$$$, performing the operation gives us $$$s = $$$ "$$$\texttt{(()(((((()))))))}$$$", which has a score of $$$6$$$. It can be shown that $$$6$$$ is the maximum possible score achievable.