有一个长度为 $$$n$$$ 的一维网格。网格的第 $$$i$$$ 个单元格包含字符 $$$s_i$$$,即“<”或“>”。
当弹球被放置在其中一个单元格上时,它会根据以下规则移动:
- 如果弹球在第 $$$i$$$ 个单元格上且 $$$s_i$$$ 为 '<',则弹球在下一秒向左移动一个单元格。如果 $$$s_i$$$ 为“>”,则向右移动一个单元格。
- 弹球移动后,字符 $$$s_i$$$ 被反转(即,如果 $$$s_i$$$ 以前是 '<',则变为 '>',反之亦然)。
- 弹球在离开网格时停止移动:无论是从左边界还是从右边界。
您需要回答 $$$n$$$ 个独立查询。在第 $$$i$$$ 个查询中,弹球将放置在第 $$$i$$$ 个单元格上。请注意,我们总是在初始网格上放置一个弹球。
对于每个查询,计算弹球离开网格需要多少秒。可以证明,弹球总是会在有限的步数内离开网格。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。
每个测试用例的第二行包含一个字符串 $$$s_1s_2 \ldots s_{n}$$$,长度为 $$$n$$$,由字符“<”和“>”组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,如果弹球最初放置在第 $$$i$$$ 个单元格上,则对于每个 $$$i$$$ ($$$1 \le i \le n$$$) 输出答案。
示例
输入 #1
3 3 ><< 4 <<<< 6 <><<<>
输出 #1
3 6 5 1 2 3 4 1 4 7 10 8 1
注意
在第一个测试用例中,$$$i=1$$$ 时弹球的运动如下图所示。弹球需要 $$$3$$$ 秒才能离开网格。
$$$i=2$$$ 时弹球的运动如下图所示。弹球需要 $$$6$$$ 秒才能离开网格。