← 返回题目列表

Codeforces · 1428/B

B. 腰带房间

中文机器翻译题面 查看原题

在蛇展中,有$$$n$$$个房间(编号为$$$0$$$到$$$n - 1$$$)排列成圆圈,每个房间里都有一条蛇。房间由 $$$n$$$ 传送带连接,第 $$$i$$$ 传送带连接房间 $$$i$$$ 和 $$$(i+1) \bmod n$$$。换句话说,房间$$$0$$$和$$$1$$$、$$$1$$$和$$$2$$$、$$$\ldots$$$、$$$n-2$$$和$$$n-1$$$、$$$n-1$$$和$$$0$$$通过传送带连接。

第 $$$i$$$ 传送带处于以下三种状态之一:

- 如果是顺时针方向,蛇只能从$$$i$$$房间到$$$(i+1)\bmod n$$$。
- 如果是逆时针方向,蛇只能从房间 $$$(i+1) \bmod n$$$ 到 $$$i$$$。
- 如果关闭,蛇可以向任一方向移动。

上面是 $$$4$$$ 房间的示例,其中皮带 $$$0$$$ 和 $$$3$$$ 关闭,$$$1$$$ 为顺时针方向,$$$2$$$ 为逆时针方向。

每条蛇都想离开它的房间并稍后再回来。如果蛇可以离开房间,然后使用传送带返回房间,则该房间可以返回。这样的可返还房间有多少间?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$):测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 300\,000$$$):房间数量。

每个测试用例描述的下一行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由 '<'、'>' 和 '-' 组成。

- 如果 $$$s_{i} = $$$ '>',则第 $$$i$$$ 传送带顺时针运行。
- 如果 $$$s_{i} = $$$ '<',则第 $$$i$$$ 传送带逆时针运行。
- 如果 $$$s_{i} = $$$ '-',则第 $$$i$$$ 传送带关闭。

保证所有测试用例中$$$n$$$的总和不超过$$$300\,000$$$。

输出

对于每个测试用例,输出可返回房间的数量。

示例

输入 #1

4
4
-><-
5
>>>>>
3
<--
2
<>

输出 #1

3
5
3
0

注意

在第一个测试用例中,除 $$$2$$$ 房间外,所有房间均可退回。房间里的蛇 $$$2$$$ 被困住了,无法出去。该测试用例对应于问题陈述中的图片。

在第二个测试用例中,所有房间都可以通过一系列顺时针传送带返回。