题目描述

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".

输入格式

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$.

输出格式

For each test case, print one line.

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

题目大意

定义一个字符串为括号串当且仅当其仅由 ( 和 ) 组成。

试将一个长度为 $n$ 的括号串分为 $2m$ 个子序列，子序列可以为空，且每个字符都必须分到恰好一个子序列中，使得至少 $m$ 个子序列为匹配的括号串。空序列不算匹配的括号序列。无解请输出 $0$，否则输出 $1$。本题多组数据，其中数据组数为 $T$。

定义 $A$ 为 $B$ 的子序列当且仅当 $A$ 能由 $B$ 在顺序不改变的前提下删除若干元素后得到。

*样例 $1$ 解释：你可以将第一个和第二个字符分入第一个子序列，让第二个子序列为空子序列。此时第一个子序列为 ()，第二个为空，总计有一个匹配的括号序列，满足要求。

2
2 1
()
2 99
()

1
0

提示

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$.