Background

“Waaah—! Why is Pac-Man coming out of my bento?!”

Kruskal-chan stared in horror at the sandwich in her hand. The densely packed sesame seeds suddenly turned into countless tiny Pac-Men, crazily moving left and right! Even stranger, bean-shaped specks of light appeared in the air and were swallowed one by one.

“Could this be the truth of the universe?” Trembling, Kruskal-chan took out her notebook and decided to calculate the minimum number of beans that would be eaten.

Problem Description

On the integer points of the segment $1 \le x \le n$, there are some beans and Pac-Men. There are two types of Pac-Men: one moves left at unit speed, and the other moves right at unit speed. When a Pac-Man passes a bean, the bean will be eaten. When two Pac-Men meet, you need to choose one Pac-Man to eat the other; the remaining Pac-Man keeps its moving direction unchanged.

Find: the minimum total number of beans that will be eaten.

Note: the positions of Pac-Men can change continuously, not discretely.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of test cases.

For each test case, the first line contains an integer, the right endpoint of the segment $n$ ($1 \le n \le 10^5$).

The next line contains a string of length $n$ consisting only of .o<>, representing an empty space, a bean, a left-moving Pac-Man, and a right-moving Pac-Man, respectively.

It is guaranteed that $\sum n \le 10^5$.

Output Format

Output $T$ lines. Each line contains one integer, the minimum total number of beans that will be eaten.

2
6
o>.<oo
2
<>

1
0

Hint

In the first sample, when two Pac-Men meet, choose to keep the left-moving Pac-Man. In this way, only the leftmost bean will be eaten in the end, so the answer is $1$.

Translated by ChatGPT 5