Description

In this problem, we define a sequence of ( and ) as a "bracket sequence".

The definition of Regular Bracket Sequence is as follows:

1. () is a Regular Bracket Sequence.
2. If A is a Regular Bracket Sequence, then (A) is also a Regular Bracket Sequence.
3. If A and B are Regular Bracket Sequences, then AB is also a Regular Bracket Sequence.

For example: (), (()), and ()() are all Regular Bracket Sequences, but )(, ()( are not.

In particular, an empty sequence is not a Regular Bracket Sequence sequence in this problem.

Now cute Ran gives you a bracket sequence $s$ of length $n$. She wants you to construct $2\cdot m$ strictly increasing arrays. Let us denote them as $p_1,p_2,\cdots,p_{2 m}$ (you can leave any of them empty). You need to ensure that all integers between $1\sim n$ appear exactly once in these arrays.

An array $p_i=\{r_1,r_2,\cdots,r_k\}$ is Beautiful if $\{s_{r_1},s_{r_2},\cdots,s_{r_k}\}$ is a Regular Bracket Sequence.

Ran wonders whether it is possible to construct these arrays so that at least $m$ of the $2\cdot m$ arrays are "beautiful arrays".

Input Format

Each test contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, and the second line contains a bracket sequence $s$.

Output Format

For each test case, print one line.

If it is possible to construct these arrays, print $1$. Otherwise print $0$.

2
2 1
()
2 99
()

1
0

Hint

Explanation

For the first test case, we can construct $p_1=\{1,2\}$ and $p_2=\{\}$. So $p_1$ is a "beautiful array".

For the second test case, it is obvious that we cannot use two numbers to construct $99$ beautiful arrays.

Constraints

$1\le T,n,m\le 200$.