给定一个长度为 (一定是偶数) 的仅含有 "(" 和 ")" 的括号序列，其中，"(" 有 个，")" 也有 个。 牛牛可以进行若干次操作，每一次操作，选择一个下标 ，然后将该下标位置上的括号移动到整个序列的开头或者末尾。 那么，牛牛最少需要操作多少次，可以将该括号序列转化成一个常规括号序列？ "()" 是一个常规括号序列； 若 是一个常规括号序列，那么 "(" + + ")" 也是一个常规括号序列； 若 是一个常规括号序列， 也是一个常规括号序列，那么 也是一个常规括号序列。

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。对于每组测试数据，第一行输入一个正整数 ，代表括号序列的长度。第二行输入一个长度为 的满足题意的括号序列。

输出描述:

对于每组测试数据，一行输出一个整数，代表需要的最小操作次数。