rt,题目如下：

1. 有效括号子序列计数

题目描述

给定一个仅由 '(' 和 ')' 组成的字符串 S，求其不同的有效括号子序列的个数。子序列不要求连续，但不同的位置选择视为不同的子序列，即使它们形成的括号序列相同。

有效括号子序列必须满足：

1. 左右括号数量相等；
2. 任意前缀中左括号数不少于右括号数。

由于答案可能很大，请输出结果对 $10^9+7$ 取模后的值。

输入格式

输入第一行包含一个整数 $T$，表示测试数据组数。
接下来 $T$ 行，每行一个字符串 $S$。

输出格式

输出 $T$ 行，每行一个整数，表示对应答案。

样例 #1

样例输入 #1

3
()
()()
(())

样例输出 #1

1
3
2

提示

样例解释

第三组数据中，字符串 (()) 的有效子序列为：

• 选取第 1 和第 2 个字符得到 ()
• 选取第 1 和第 4 个字符得到 ()
• 选取第 2 和第 3 个字符得到 ()
• 选取第 3 和第 4 个字符得到 ()
• 选取所有字符得到 (())
  总共有 $5$ 个，但样例输出为 $2$。注意题目中子序列需满足有效条件，例如选取第 1 和第 4 个字符时，前缀顺序为 ()，满足条件。

数据范围

对于所有测试点，保证 $1 \leq T \leq 10$，$1 \leq |S| \leq 1000$。

---

2. 最长重复子串

题目描述

给定一个字符串 $S$ 和一个整数 $k$，找出 $S$ 中最长的子串，该子串至少出现 $k$ 次（出现位置可以重叠）。若存在多个最长子串，输出任意一个；若不存在，输出 -1。

输入格式

第一行输入整数 $T$，表示数据组数。
每组数据包含两行：第一行为字符串 $S$，第二行为整数 $k$。

输出格式

输出 $T$ 行，每行一个字符串或 -1。

样例 #1

样例输入 #1

2
ababa
2
aaaaa
3

样例输出 #1

aba
aaa

提示

数据范围

对于所有测试点，保证 $1 \leq T \leq 10$，$2 \leq k \leq |S|$，$1 \leq |S| \leq 10^4$。

---

3. 分割回文串 II

题目描述

给定一个字符串 $S$，将其分割成若干子串，使得每个子串都是回文。求最少需要分割几次。若无法分割，输出 -1。

输入格式

第一行输入整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个字符串 $S$。

输出格式

输出 $T$ 行，每行一个整数。

样例 #1

样例输入 #1

3
aab
a
ab

样例输出 #1

1
0
-1

提示

数据范围

对于所有测试点，保证 $1 \leq T \leq 10$，$1 \leq |S| \leq 1000$。

---

4. 编辑距离

题目描述

给定两个字符串 $A$ 和 $B$，求将 $A$ 转换为 $B$ 所需的最小操作次数。允许的操作包括：插入一个字符、删除一个字符、替换一个字符。

输入格式

第一行输入整数 $T$，表示数据组数。
每组数据包含两行：第一行为字符串 $A$，第二行为字符串 $B$。

输出格式

输出 $T$ 行，每行一个整数。

样例 #1

样例输入 #1

2
kitten
sitting
abc
abd

样例输出 #1

3
1

提示

数据范围

对于所有测试点，保证 $1 \leq T \leq 10$，$1 \leq |A|, |B| \leq 1000$。