"Wow! Why are Pac-Men crawling out of my bento box!"

Kruskal-chan looked in horror at the sandwich in her hand, where the dense sesame seeds had suddenly turned into countless tiny Pac-Men, moving frantically left and right! Even more bizarrely, bean-shaped light spots appeared in the air, being devoured by them one by one.

"Is this the truth of the universe?" Kruskal-chan tremblingly took out her notebook, deciding to calculate the minimum number of beans that would be eaten...

Some beans and Pac-Men are distributed on the integer points of the line segment $1 \le x \le n$. There are two types of Pac-Men: one moving to the left at unit speed, and one moving to the right at unit speed. When a Pac-Man passes a bean, the bean is eaten. When two Pac-Men meet, you must choose one of them to eat the other, and the remaining Pac-Man continues to move in its original direction.

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

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

Input

This problem contains multiple test cases.

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

Each test case starts with a line containing an integer $n$ ($1 \le n \le 10^5$), representing the right endpoint of the line segment.

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

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

Output

Output $T$ lines, each containing an integer representing the minimum total number of beans eaten.

Examples

Input 1

2
6
o>.<oo
2
<>

Output 1

1
0

Note

In the first example, when the two Pac-Men meet, choosing to keep the one moving to the left results in only the leftmost bean being eaten, so the answer is 1.