← 返回题目列表

Codeforces · 1837/B

B. 比较字符串

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中每个字符为 < 或 >。

由$$$n+1$$$元素组成的数组$$$a$$$与字符串$$$s$$$兼容,如果对于从$$$1$$$到$$$n$$$的每个$$$i$$$,字符$$$s_i$$$表示比较$$$a_i$$$和$$$a_{i+1}$$$, i的结果。即:

- $$$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 \le t \le 500$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$);
- 第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成。 $$$s$$$ 的每个字符都是 < 或 >。

输出

对于每个测试用例,打印一个整数 - 与给定字符串 $$$s$$$ 兼容的所有数组中的最小成本。

示例

输入 #1

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

输出 #1

3
3
6
2

注意

在示例的第一个测试用例中,数组可以是 $$$[13, 37, 42, 37, 13]$$$。

在示例的第二个测试用例中,数组可以是 $$$[42, 37, 13, 37, 42]$$$。