题目描述

邓少的笔记本上有一个长度为 $n$ 的括号序列 $S$。$S$ 仅由 $\texttt{()*}$ 三种字符组成，其中 $\texttt{*}$ 可以变化成一个 $\texttt{(}$ 或 $\texttt{)}$。

邓少认为一个括号序列是“好的”，当且仅当它满足以下条件：

对于该序列中 $\texttt{*}$ 的所有可能的变化，都存在一种在这个序列末尾恰好添加 $k$ 个任意括号的方式，使得整个序列成为合法的括号序列。

例如，当 $k=3$ 时，括号序列 $\texttt{(*(}$ 是“好的”。因为：

• 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足上述条件；
• 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{()()()}$ 满足上述条件。

而当 $k=3$ 时，括号序列 $\texttt{*((}$ 不是“好的”。因为当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，没有任何一种在末尾恰好添加 $k$ 个任意括号的方式能使该括号序列合法。

需要注意的是，每个 $\texttt{*}$ 可独立变成任意一个括号。也就是说，每一个 $\texttt{*}$ 的变化情况都不会对其他任何 $\texttt{*}$ 的变化造成影响。

现在邓少找到了你，希望你告诉他，有多少个不同的 $0 \le x < n$ 满足：将这个括号序列循环左移 $x$ 位后，形成的括号序列是“好的”。

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含两个正整数 $n,k$，含义如题所示。

第二行包含一个长为 $n$ 的字符串 $S$，表示该括号序列。保证 $S$ 仅由 $\texttt{(}$、$\texttt{)}$ 和 $\texttt{*}$ 三种字符组成。

输出格式

对于每组测试数据：

输出一行，包含一个整数，表示满足条件的 $x$ 的数量。

3
3 3
((*
5 1
()(**
10 8
(**)(((((*

2
0
3

提示

【样例解释】

对于第一组测试数据：

• $x = 0$，此时括号序列为 $\texttt{((*}$。

  • 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求；
  • 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{(()())}$ 满足要求。

• $x = 1$，此时括号序列为 $\texttt{(*(}$。

  • 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求；
  • 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{()()()}$ 满足要求。

• $x = 2$，此时括号序列为 $\texttt{*((}$。

  • 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求；
  • 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，括号序列为 $\texttt{)((}$，无法通过在序列末尾添加 $3$ 个括号使其变为合法括号序列。因此，$x=2$ 不合法。

综上，有两个 $x$ 满足要求，答案为 $2$。

对于第二组测试数据，不存在任何一种方法能满足要求。

对于第三组测试数据，只有 $x = 4,5,6$ 满足要求。

【数据范围】

对于所有测试数据，保证：

• $1 \le T \le 10$；
• $1 \le n,k \le 10^6$；
• $(n+k) \bmod 2 = 0$；
• $S$ 仅由 $\texttt{()*}$ 三种字符组成。

• 特殊性质 $A$：保证 $n = k$。
• 特殊性质 $B$：保证 $S$ 仅由 $\texttt{(}$ 和 $\texttt{)}$ 组成。
• 特殊性质 $C$：保证 $S$ 仅由 $\texttt{(}$ 和 $\texttt{*}$ 组成。