题目内容

一个嵌套结构由一个字符串 $s$ 表示，字符串仅由两种字符 ( 和 ) 组成。( 表示进入一层结构，) 表示离开当前层。我们称一个字符串是良构的，当且仅当：空字符串是良构的；若 $A$ 是良构字符串，则 ( $A$ ) 也是良构字符串；若 $A$ 和 $B$ 都是良构字符串，则 $AB$ 也是良构字符串。

对于任意良构字符串，从左到右扫描，可以定义每个字符的所在层数：遇到 ( 时，当前层数加 1，该字符的所在层数为加后的值；遇到 ) 时，该字符的所在层数为当前层数，然后当前层数减 1。记整个字符串中所有字符的最大所在层数为 $D$。

现在开始按轮次移除字符。每一轮，先对当前字符串重新计算每个字符的所在层数，然后同时移除所有所在层数最大的字符。剩余字符保持原来的相对顺序，形成新的字符串，进入下一轮。可以证明，若一个字符在原字符串中的所在层数为 $d$，则它会在第 $D-d+1$ 轮被移除。

请你对原字符串中的每个字符，输出它会在第几轮被移除。

约束：测试数据组数 $T$ 满足 $1 \le T \le 10^4$。每组数据中的字符串长度 $n$ 为偶数且 $2 \le n \le 2 \times 10^5$。单个测试文件中所有字符串长度之和不超过 $2 \times 10^5$。字符串仅由字符 ( 和 ) 组成，且保证是良构的。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。 接下来每组数据包含两行： 第一行输入一个整数 $n$，表示当前良构字符串的长度。 第二行输入一个长度为 $n$ 的字符串，仅由字符 ( 和 ) 组成，保证是良构的。

输出描述

对于每组测试数据，输出一行 $n$ 个整数，用空格分隔。第 $i$ 个整数表示原字符串中第 $i$ 个字符在第几轮被移除。

样例1

输入

1
6
(()())

输出

2 1 1 1 1 2

说明

按题意模拟计算得到。

样例2

输入

1
6
(()())
6

输出

2 1 1 1 1 2

说明

按题意模拟计算得到。