Xếp hàng đàn cừu

Một màn chơi được mô tả bằng một xâu độ dài $n$ gồm các kí tự '.' (ô trống) và '*' (một con cừu).

Trong một nước đi, bạn có thể di chuyển một con cừu sang ô liền kề bên trái hoặc bên phải, với điều kiện ô đó tồn tại và đang trống.

Màn chơi kết thúc khi tất cả các con cừu đứng liền nhau, tức là giữa hai con cừu bất kì không còn ô trống nào.

Với mỗi màn chơi cho trước, hãy tính số nước đi tối thiểu để hoàn thành nó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$.
  • Dòng thứ hai chứa xâu độ dài $n$ gồm các kí tự '.' và '*'.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa số nước đi tối thiểu cần thực hiện.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^6$
• Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^6$.

Ví dụ