每次测试的时间限制：$2$ 秒
每次测试的内存限制：$256$ 兆字节

有一条长度为 $n$ 的一维网格。网格的第 $i$ 个格子包含一个字符 $s_i$，该字符要么是 '<'，要么是 '>'。

当一个弹球被放置在某个格子上时，它按照以下规则移动：

• 如果弹球位于第 $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$）。

第二行包含一个长度为 $n$ 的字符串 $s_1 s_2 \ldots s_n$，由字符 '<' 和 '>' 组成。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出

对于每个测试用例，对于每个 $i$（$1 \le i \le n$），输出如果弹球初始放置在第 $i$ 格时所需的秒数。每个测试用例的输出占一行，数之间用空格分隔。

示例

输入

3
3
><<
4
<<<<
6
<><<<>

输出

3 6 5
1 2 3 4
1 4 7 10 8 1

注意

在第一个测试用例中（$n=3$，$s=\texttt{><<}$），弹球从第 $1$ 格出发需要 $3$ 秒离开网格， 从第 $2$ 格出发需要 $6$ 秒，从第 $3$ 格出发需要 $5$ 秒。