题目描述

给定一个长度为 $n$ 的括号序列 $S$。$S$ 仅由 (、) 和 * 三种字符组成，其中每个 * 都可以独立地变为一个 ( 或 )（每一个 * 的变化情况都不会对其他任何 * 造成影响）。

我们认为一个括号序列是“好的”，当且仅当它满足以下条件： 对于该序列中所有的 * 的每一种可能的变化，都一定存在一种在这个序列末尾恰好添加 $k$ 个任意括号的方式，使得整个序列成为合法的括号序列。

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

• 当 * 变化成 ( 时，序列变为 (((，可以在末尾添加 ))) 使其成为合法的 ((()))；
• 当 * 变化成 ) 时，序列变为 ()(，可以在末尾添加 )() 使其成为合法的 ()()()。

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

现在，请你计算出有多少个不同的整数 $x$（$0 \le x < n$），满足：将括号序列 $S$ 循环左移 $x$ 位后，形成的新括号序列是“好的”。

输入格式

本题有多组测试数据。

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

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

• 第一行包含两个正整数 $n, k$。
• 第二行包含一个长为 $n$ 的字符串 $S$，表示该括号序列。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件的 $x$ 的数量。

样例输入 1

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

样例输出 1

2
0
3

说明

样例解释

对于第一组测试数据：

• $x = 0$，此时循环左移后的括号序列为 ((*。
  • 当 * 变化成 ( 时，存在括号序列 ((())) 满足要求；
  • 当 * 变化成 ) 时，存在括号序列 (()()) 满足要求。
• $x = 1$，此时括号序列为 (*(。
  • 当 * 变化成 ( 时，存在括号序列 ((())) 满足要求；
  • 当 * 变化成 ) 时，存在括号序列 ()()() 满足要求。
• $x = 2$，此时括号序列为 *((。
  • 当 * 变化成 ( 时，存在括号序列 ((())) 满足要求；
  • 当 * 变化成 ) 时，括号序列为 )((，无法通过在末尾添加 $3$ 个括号使其变为合法括号序列。因此，$x=2$ 不合法。

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

对于第二组测试数据，不存在任何一个 $x$ 能满足要求。

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

数据范围

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

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

各测试点的附加限制如下表所示：

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