310460: CF1837B. Comparison String

B. Comparison Stringtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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$.

ExampleInput

4
4
<<>>
4
>><<
5
>>>>>
7
<><><><

Output

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]$.

题目大意：
给定一个长度为n的字符串s，其中每个字符要么是“<”，要么是“>”。一个包含n+1个元素的数组a如果与字符串s兼容，那么对于每个i（从1到n），字符s_i代表a_i和a_{i+1}的比较结果，即：

- 如果s_i是“<”，则a_i < a_{i+1}；
- 如果s_i是“>”，则a_i > a_{i+1}。

例如，数组[1, 2, 5, 4, 2]与字符串“<<>>”兼容。与该字符串兼容的其他数组例如[13, 37, 42, 37, 13]。

数组的成本是数组中不同元素的数量。例如，数组[1, 2, 5, 4, 2]的成本是4；数组[13, 37, 42, 37, 13]的成本是3。

计算与给定字符串s兼容的所有数组中的最小成本。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 500）——测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数n（1 ≤ n ≤ 100）；
- 第二行包含一个由n个字符组成的字符串s。s的每个字符要么是“<”，要么是“>”。

输出：
- 对于每个测试用例，打印一个整数——与给定字符串s兼容的所有数组中的最小成本。题目大意： 给定一个长度为n的字符串s，其中每个字符要么是“<”，要么是“>”。一个包含n+1个元素的数组a如果与字符串s兼容，那么对于每个i（从1到n），字符s_i代表a_i和a_{i+1}的比较结果，即： - 如果s_i是“<”，则a_i < a_{i+1}； - 如果s_i是“>”，则a_i > a_{i+1}。 例如，数组[1, 2, 5, 4, 2]与字符串“<<>>”兼容。与该字符串兼容的其他数组例如[13, 37, 42, 37, 13]。 数组的成本是数组中不同元素的数量。例如，数组[1, 2, 5, 4, 2]的成本是4；数组[13, 37, 42, 37, 13]的成本是3。 计算与给定字符串s兼容的所有数组中的最小成本。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 500）——测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数n（1 ≤ n ≤ 100）； - 第二行包含一个由n个字符组成的字符串s。s的每个字符要么是“<”，要么是“>”。 输出： - 对于每个测试用例，打印一个整数——与给定字符串s兼容的所有数组中的最小成本。