Phòng nối băng chuyền

Có $n$ căn phòng được đánh số từ $0$ đến $n-1$ xếp thành một vòng tròn, mỗi phòng có một con rắn. Các phòng được nối với nhau bởi $n$ băng chuyền: băng chuyền thứ $i$ nối phòng $i$ và phòng $(i+1)modn$. Như vậy các cặp phòng $0$ và $1$, $1$ và $2$, ..., $n-2$ và $n-1$, $n-1$ và $0$ được nối với nhau.

Băng chuyền thứ $i$ đang ở một trong ba trạng thái:

• Nếu quay theo chiều kim đồng hồ, rắn chỉ có thể đi từ phòng $i$ sang phòng $(i+1)modn$.
• Nếu quay ngược chiều kim đồng hồ, rắn chỉ có thể đi từ phòng $(i+1)modn$ sang phòng $i$.
• Nếu tắt, rắn có thể đi theo cả hai chiều.

Mỗi con rắn muốn rời phòng của mình rồi sau đó quay trở lại. Một phòng được gọi là quay-về-được nếu con rắn trong phòng đó có thể rời khỏi phòng và sau đó quay trở lại chính phòng đó bằng cách di chuyển qua các băng chuyền. Hãy đếm số phòng quay-về-được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa số nguyên $n$: số phòng.
  • Dòng sau chứa xâu $s$ độ dài $n$ gồm các ký tự >, <, -:
    • $s_i=$ >: băng chuyền thứ $i$ quay theo chiều kim đồng hồ.
    • $s_i=$ <: băng chuyền thứ $i$ quay ngược chiều kim đồng hồ.
    • $s_i=$ -: băng chuyền thứ $i$ tắt.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa số phòng quay-về-được.

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le 300000$
• Tổng của $n$ trên tất cả các bộ test không vượt quá $300000$.

Ví dụ