题目背景

English statement. You must submit your code at the Chinese version of the statement.

我已经知道，在设置好循环播放时就已经知道，我是在麻痹自己，在逃避问题。

我承认如此，可捞起那些沉于水底的细节时，却一瞬间突然和所有所有真实的心跳共鸣。

那时总想的太少，现在常想得太多，不知所措似荒塘里的绿藻蔓延着。

然而这世间情感太多，小 R 也只能体会更开心和更难过。

题目描述

小 R 想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。

小 R 有 $n$ 个未知量 $a_1\dots a_n$，对每个 $1 \leq i < n$，她都比较了 $a_i$ 和 $a_{i+1}$ 并写下了一个字符 $c_i \in \{\texttt <, \texttt >, \texttt =\}$，表示两个未知量之间的比较结果。具体地：

• 若 $c_i = \texttt >$，则 $a_i > a_{i+1}$；
• 若 $c_i = \texttt <$，则 $a_i < a_{i+1}$；
• 否则（$c_i = \texttt =$），表示 $a_i = a_{i+1}$。

小 R 称 $\bm{a_i}$ 比 $\bm{a_j}$ 更开心，当且仅当对任何 满足上述 $\bm{n - 1}$ 条约束的 $[a_1, \dots, a_n] \in \mathbb R^n$，都有 $a_i < a_j$。请你帮她数出 $1 \leq i, j \leq n$ 且 $a_i$ 比 $a_j$ 更开心的整数数对 $(i, j)$ 个数。

因为要循环播放，所以有多组数据。

输入格式

本题有多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 第一行一个整数 $n$。
• 接下来一行，一个长度为 $n - 1$ 的字符串 $c_1c_2\dots c_{n-1}$。

输出格式

对于每组数据，输出仅一行一个整数，表示符合条件的整数数对个数。

5
5
<<<<
7
<=><=<
9
=<<><==<
11
>=<<=>>>=>
13
=><<=<=>=><>

10
9
13
29
25

提示

样例解释

• 对于第一组数据，$a_i$ 比 $a_j$ 开心当且仅当 $1 \leq i < j \leq n$，故共有 $\frac{5\times 4}{2} = 10$ 对合法的 $(i, j)$。
• 对于第二组数据，合法的 $(i, j)$ 分别为：$(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (5, 7), (6, 7)$，共 $9$ 对。
• 对于其他几组数据，聪明的读者可以自行验证。

数据规模与约定

本题采用捆绑测试和子任务依赖。

• Subtask 0（0 pts）：样例。
• Subtask 1（10 pts）：$n \leq 8$，$T \leq 8$。
• Subtask 2（20 pts）：$n \leq 5000$，$T \leq 8$。依赖于子任务 $0, 1$。
• Subtask 3（20 pts）：$c_i \neq \texttt =$。
• Subtask 4（50 pts）：无特殊限制。依赖于子任务 $0 \sim 3$。

对于所有数据，保证 $2 \leq n \leq 2\times 10^5$，$1 \leq T \leq 10^4$，$c_i \in \{\texttt <, \texttt >, \texttt =\}$，$\sum n \leq 5\times 10^5$。