Counting Forced Order Pairs

In this problem, we have (n) unknowns (a_1, a_2, \dots, a_n). For each (1 \le i < n) a character (c_i \in {<, >, =}) is recorded to indicate the relationship between (a_i) and (a_{i+1}) as follows:

• If \(c_i = <\), then \(a_i < a_{i+1}\).
• If \(c_i = >\), then \(a_i > a_{i+1}\).
• If \(c_i = =\), then \(a_i = a_{i+1}\).

We say that (a_i) is happier than (a_j) (i.e. (a_i < a_j)) if and only if for any real numbers (a_1, a_2, \dots, a_n) satisfying the above (n-1) constraints we have (a_i < a_j) always true.

Your task is to count the number of ordered pairs ((i, j)) with (1 \le i, j \le n) such that (a_i) is forced to be less than (a_j) in every assignment satisfying the constraints.

Note: The input contains multiple test cases.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. For each test case:

1. The first line contains an integer \(n\) (the number of unknowns).
2. If \(n \gt 1\), the next line contains a string of length \(n-1\) consisting only of characters '', '=' which represent the comparisons between consecutive elements.

outputFormat

For each test case, output a single integer denoting the number of ordered pairs \((i, j)\) such that \(a_i < a_j\) is forced by the given constraints.

sample

3
3
<<
5
<==<

3
1
7