我们称一个括号序列为“平衡的括号序列”，当且仅当满足以下归纳定义： 1) 空串是平衡的； 2) 若字符串 是平衡的，则“”是平衡的； 3) 若字符串 与 均是平衡的，则“”是平衡的（表示连接）。 例如：括号序列 与 是平衡的；而 、、 不是。 给定一个偶数长度的括号序列 s（仅包含 '(' 与 ')'）。你可以进行若干次如下操作： 选择一个位置 ，交换相邻的两个字符 与 。 请你计算，最少需要进行多少次这样的相邻交换，才能使整个序列变为一个平衡的括号序列。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入一个偶数 ； 第二行输入一个长度为 的字符串 （仅包含 '(' 与 ')'）。 保证所有测试中 的总和不超过 ,保证每组数据一定可以通过相邻交换变为平衡序列。

输出描述:

对于每组测试数据，输出一行一个整数，表示将 s 变为平衡括号序列所需的最少相邻交换次数。