P16124 [USTCPC 2026] Line of Pac-Man

“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.

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.

**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 $T$ lines. Each line contains one integer, the minimum total number of beans that will be eaten.

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