Description

在这个问题中，我们将由 ( 和 ) 组成的序列定义为“括号序列”。

正规括号序列 的定义如下：

1. () 是一个正规括号序列。
2. 如果 A 是一个正规括号序列，那么 (A) 也是一个正规括号序列。
3. 如果 A 和 B 是正规括号序列，那么 AB 也是一个正规括号序列。

例如：(), (()) 和 ()() 都是正规括号序列，但 )(, ()( 不是。

特别地，在这个问题中，空序列不是一个正规括号序列。

现在，可爱的 Ran 给你一个长度为 $n$ 的括号序列 $s$。她希望你构造 $2 \cdot m$ 个严格递增的数组。我们将它们记作 $p_1,p_2,\cdots,p_{2m}$（你可以将其中任何一个留空）。你需要确保所有从 $1\sim n$ 的整数在这些数组中恰好出现一次。

一个数组 $p_i=\{r_1,r_2,\cdots,r_k\}$ 是美丽的，如果 $\{s_{r_1},s_{r_2},\cdots,s_{r_k}\}$ 是一个正规括号序列。

Ran 想知道是否有可能构造这些数组，使得 $2 \cdot m$ 个数组中至少 $m$ 个是“美丽数组”。

Input Format

每个测试包含多个测试用例。

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，第二行包含一个括号序列 $s$。

Output Format

对于每个测试用例，输出一行。

如果可以构造这些数组，输出 $1$。否则输出 $0$。

2
2 1
()
2 99
()

1
0

Hint

解释

对于第一个测试用例，我们可以构造 $p_1=\{1,2\}$ 和 $p_2=\{\}$。所以 $p_1$ 是一个“美丽数组”。

对于第二个测试用例，很明显我们不能用两个数字构造 $99$ 个美丽数组。

约束

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

题面翻译由 ChatGPT-4o 提供。