题目内容

$TK$ 得到一个合法括号串 $s$。接下来这个括号串会按轮次逐渐消失。

在每一轮中，当前括号串里所有深度最大的括号对会同时消失。消失后，剩余括号保持原来的相对顺序，形成新的括号串，继续下一轮。

这里括号对的深度定义为它被多少层括号包含再加 $1$。例如，字符串 "((())())" 中最外层括号深度为 $1$，里面两对括号深度为 $2$。

请你对原字符串中的每一个字符，输出它会在第几轮消失。

合法括号串：一个括号串被称为合法的括号串，当且仅当：

1. 空串是合法的括号；
2. 如果 $A$ 是合法的括号串，那么 (A) 也是合法的括号串；
3. 如果 $A$ 和 $B$ 都是合法的括号串，那么 $AB$ 也是合法的括号串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(2 \le n \le 2\times 10^5)$，表示括号串长度。
• 第二行输入一个长度为 $n$ 的合法括号串 $s$，仅由 ( 和 ) 组成。

保证 $n$ 为偶数，且单个测试文件中 $n$ 之和不超过 $2\times 10^5$。

输出描述

对于每一组测试数据，新起一行输出 $n$ 个整数，第 $i$ 个整数表示原字符串中第 $i$ 个字符会在第几轮消失。

样例1

输入

3
6
(()())
6
((()))
10
(()((())))

输出

2 1 1 1 1 2
3 2 1 1 2 3
4 3 3 3 2 1 1 2 3 4