「Wdcfr-1」Beautiful Array

定义一个字符串为括号串当且仅当其仅由 `(` 和 `)` 组成。 试将一个长度为 $n$ 的括号串分为 $2m$ 个子序列，子序列可以为空，且每个字符都必须分到恰好一个子序列中，使得至少 $m$ 个子序列为匹配的括号串。**空序列不算匹配的括号序列**。无解请输出 $0$，否则输出 $1$。本题多组数据，其中数据组数为 $T$。 定义 $A$ 为 $B$ 的子序列当且仅当 $A$ 能由 $B$ 在顺序不改变的前提下删除若干元素后得到。 *样例 $1$ 解释：你可以将第一个和第二个字符分入第一个子序列，让第二个子序列为空子序列。此时第一个子序列为 `()`，第二个为空，总计有一个匹配的括号序列，满足要求。

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. 1. If `A` is a Regular Bracket Sequence, then `(A)` is also a Regular Bracket Sequence. 1. 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$.

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