Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Comparison String

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Example

Input

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:29:22 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|