说明

给定一个括号串 S ，规定其前缀若满足以下条件之一，则删去。

1. 是合法的括号串（ 每个左括号都能找到右括号与其对应 ）
2. 是长度至少为2的回文串

若有多个前缀满足这个条件，优先删去最小的前缀。
重复进行这个操作，直到所有的前缀都不满足这两个条件的任意一个，求删除了几次？最后还剩下多少个字符？

输入格式

输入的第一行包含一个正整数T ， 代表数据的组数。
下面T组数据，每组数据占两行。
第一行为括号串的长度n <= 5 * 10^5
第二行是括号串 S

输出格式

输出为一行包括两个整数，分别代表删除的次数和剩余的字符数

样例

5
2
()
3
())
4
((((
5
)((()
6
)((()(

1 0
1 1
2 0
1 0
1 1