CF1837B.Comparison String
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 si represents the result of comparing ai and ai+1 , i. e.:
- si is < if and only if ai<ai+1 ;
- si is > if and only if ai>ai+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 .
输入格式
The first line contains one integer t ( 1≤t≤500 ) — the number of test cases.
Each test case consists of two lines:
- the first line contains one integer n ( 1≤n≤100 );
- the second line contains the string s , consisting of n characters. Each character of s is either < or >.
输出格式
For each test case, print one integer — the minimum cost among all arrays which are compatible with the given string s .
输入输出样例
输入#1
4 4 <<>> 4 >><< 5 >>>>> 7 <><><><
输出#1
3 3 6 2
说明/提示
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] .