正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:
- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。
给定两个字符串 $$$s$$$ 和 $$$a$$$,字符串 $$$s$$$ 的长度为 $$$n$$$,字符串 $$$a$$$ 的长度为 $$$n - 3$$$。字符串 $$$s$$$ 是一个括号序列(即该字符串的每个元素都是左括号字符或右括号字符)。字符串 $$$a$$$ 是一个二进制字符串(即该字符串的每个元素不是 1 就是 0)。
字符串 $$$a$$$ 对字符串 $$$s$$$ 施加了一些约束:对于每个 $$$i$$$ ,使得 $$$a_i$$$ 为 1,字符串 $$$s_i s_{i+1} s_{i+2} s_{i+3}$$$ 应该是常规括号序列。 $$$a$$$ 等于 0 的字符不会施加任何限制。
最初,字符串 $$$s$$$ 可能满足也可能不满足这些约束。您可以多次执行以下操作:将 $$$s$$$ 的某些字符替换为其反义字符(即,您可以将左括号替换为右括号,反之亦然)。
确定是否可以更改 $$$s$$$ 中的某些字符,使其满足所有约束,如果可以,计算要更改的最小字符数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成。第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 2 \cdot 10^5$$$)。第二行包含字符串 $$$s$$$,恰好由 $$$n$$$ 个字符组成; $$$s$$$ 的每个字符都是“(”或“)”。第三行包含字符串 $$$a$$$,恰好由 $$$n - 3$$$ 个字符组成; $$$a$$$ 的每个字符不是“1”就是“0”。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数:$$$s$$$ 中需要更改的最小字符数,如果不可能,则打印 $$$-1$$$。
示例
输入 #1
6 4 ))(( 1 4 ))(( 0 4 ()() 0 6 ))(()( 101 6 ))(()( 001 5 ((((( 11
输出 #1
2 0 0 4 1 -1