Comparison String
Description
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$.
谷歌翻译
给您一个长度为 的字符串 ，其中每个字符都是 < 或 >。
如果对于从 到 的每个 ，字符 表示比较 和 ，i。即：
- 是 < 当且仅当 ；
- 是 > 当且仅当 。
例如，数组 与字符串 <<>> 兼容。还有其他与该字符串兼容的数组，例如 。
数组的成本是其中不同元素的数量。例如， 的成本是 ； 的成本是 。
您必须计算与给定字符串 兼容的所有数组中的最小成本。
Input
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
For each test case, print one integer — the minimum cost among all arrays which are compatible with the given string $s$.
4
4
<<>>
4
>><<
5
>>>>>
7
<><><><
3
3
6
2
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]$.
相关
在下列比赛中: