Comparison String
Contest: Educational Codeforces Round 149 (Rated for Div. 2)
Difficulty rating: 900
Tags: greedy

You are given a string $$$s$$$ of length $$$n$$$, where each character is either < or >.

An array $$$a$$$ consisting of $$$n+1$$$ elements is compatible with the string $$$s$$$ if, for every $$$i$$$ from $$$1$$$ to $$$n$$$, the character $$$s_i$$$ represents the result of comparing $$$a_i$$$ and $$$a_{i+1}$$$, i. e.:

- $$$s_i$$$ is < if and only if $$$a_i < a_{i+1}$$$;
- $$$s_i$$$ is > if and only if $$$a_i > a_{i+1}$$$.

For example, the array $$$[1, 2, 5, 4, 2]$$$ is compatible with the string <<>>. There are other arrays with are compatible with that string, for example, $$$[13, 37, 42, 37, 13]$$$.

The cost of the array is the number of different elements in it. For example, the cost of $$$[1, 2, 5, 4, 2]$$$ is $$$4$$$; the cost of $$$[13, 37, 42, 37, 13]$$$ is $$$3$$$.

You have to calculate the minimum cost among all arrays which are compatible with the given string $$$s$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$);
- the second line contains the string $$$s$$$, consisting of $$$n$$$ characters. Each character of $$$s$$$ is either < or >.

Output format:
For each test case, print one integer — the minimum cost among all arrays which are compatible with the given string $$$s$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case of the example, the array can be $$$[13, 37, 42, 37, 13]$$$.

In the second test case of the example, the array can be $$$[42, 37, 13, 37, 42]$$$.

Example input:
4
4
<<>>
4
>><<
5
>>>>>
7
<><><><

Example output:
3
3
6
2

Editorial:
Suppose there is a segment of length $$$k$$$ that consists of equal characters in $$$s$$$. This segment implies that there are at least $$$k+1$$$ distinct values in the answer: for example, if the segment consists of < signs, the first element should be less than the second element, the second element should be less than the third element, and so on, so the corresponding segment of the array $$$a$$$ contains at least $$$k+1$$$ different elements.
So, the answer is at least $$$m+1$$$, where $$$m$$$ is the length of the longest segment of the string that consists of equal characters. Can we construct the array $$$a$$$ which will contain exactly $$$m+1$$$ distinct values? It turns out we can do it with the following greedy algorithm: let's use integers from $$$0$$$ to $$$m$$$ for our array $$$a$$$, and let's construct it from left to right; every time we place an element, we choose either the largest possible integer we can use (if the next character is >) or the smallest possible integer we can use (if the next character is <). For example, for the string <><<<>, the first $$$6$$$ elements of the array will be $$$[0, 3, 0, 1, 2, 3]$$$ (and we can use any integer from $$$0$$$ to $$$2$$$ in the last position). That way, whenever a segment of equal characters begins, the current value in the array will be either $$$m$$$ or $$$0$$$, and we will be able to decrease or increase it $$$m$$$ times, so we won't arrive at a situation where, for example, the current value is $$$0$$$ and we have to find a smaller integer.
So, the problem basically reduces to finding the longest contiguous subsegment of equal characters in $$$s$$$.