题目描述

ACM 是一个聪明的男孩，他从传统的石头-剪刀-布游戏中发明了一种新游戏。

在这个游戏中，若干个孩子围坐成一圈，每人展示一种手势（石头、剪刀或布），且在整个游戏过程中不可更改。然后随机选择一个孩子（称为玩家 A），将其手势与逆时针方向相邻的孩子（称为玩家 B）的手势进行比较。输的一方将被淘汰出圈。这一过程持续进行，直到圈中只剩一个孩子，即为胜者。显然，胜者既取决于孩子们的手势，也取决于比较的顺序。你的任务是计算所有可能的胜者总数。

游戏规则如下：

1. 剪刀（F）胜布（C）。
2. 布（C）胜石头（S）。
3. 石头（S）胜剪刀（F）。
4. 如果平局，玩家 A 胜出。

输入格式

• 输入包含多个测试用例。
• 每个用例的第一行是一个整数 $N$（孩子数量，$1 \leq N \leq 1000$）。
• 第二行包含 $N$ 个大写字母（'S'、'F' 或 'C'），以空格分隔，表示孩子们顺时针方向的手势序列。其中：
  • 'S' 表示石头（Stone），
  • 'F' 表示剪刀（Forfex），
  • 'C' 表示布（Cloth）。

输出格式

• 对于每个测试用例，输出一行，表示可能的胜者总数。

示例输入 1

3
C S F
2
S C
4
S S S S

示例输出 1

3
1
4

题目来源

POJ Monthly, 汪艺杰