[BeiJing2011]符环

在能够炼制魔力强大的法杖之后，Magic Land 上的人们逐渐意识到，强大的魔力并不一定能带来好处。破坏性的高魔力释放，反而给整个大陆蒙上了恐怖的阴影。

于是，人们开始追求可控的魔力释放。这种控制魔力释放的技术，就是如今所说的“魔法”。在远古时期，魔法由法师们口口相传。由于当时没有良好的记录方法，许多古代魔法如今已经成为传说。

后来，天才法师 Ferdinand 发明了一种记录魔法的方法：取一条由特殊材料制成的带子，其正反面均有 $1$ 行 $N$ 列格子。将带子的一端扭转 $180^\circ$ 后与另一端粘合，就得到了一个只有一面的环，称为“符环”（Spell Ring）。

符环上有一个格子被指定为起始位，同时标有起始方向。由此可以为环上的所有格子编号：起始位编号为 $0$ ，沿起始方向移动一格到达编号为 $1$ 的格子。整个符环共有 $2N$ 个格子。对于 $0\le i<2N$ ，编号为 $i$ 的格子的背面对应编号为 $(i+N)\bmod (2N)$ 的格子。

法师们使用由魔法标记“（”和“）”组成的字符串表示魔法。所有魔法对应的字符串都是合法括号序列，并且每个合法括号序列都对应一种魔法。合法括号序列的长度一定是偶数，因此可以将一种魔法写在符环上：从起始格开始，沿起始方向依次写入各个魔法标记。

符环所使用的特殊材料会根据格子两面的魔法标记呈现不同颜色。如果一个格子两面写有相同的魔法标记，即假设带子透明时两个标记恰好重合，那么该格子会呈现绯红色（Scarlet）；如果两面的魔法标记不同，则会呈现深蓝色（Deep blue）。

现在，你得到了一些古代符环。由于年代久远，符环上的魔法标记已经模糊不清，但格子的颜色仍然保存完好。请根据给定的颜色信息，计算每个符环可能对应多少种不同的魔法。

输入格式

第一行包含一个正整数 $T$ ，表示符环的数量。

接下来 $T$ 行，每行包含一个符环的颜色信息，即一个长度为 $N$ 、仅由大写字母 S 和 D 组成的字符串。其中，S 表示绯红色，D 表示深蓝色。字符串从左到右依次表示编号为 $0,1,\ldots,N-1$ 的格子的颜色。

输出 $T$ 行，每行包含一个非负整数，表示对应符环可能记录的不同魔法数量。

3
D
SSD
SDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSD

1
1
0

第一张符环唯一对应的魔法为“（）”。

第二张符环唯一对应的魔法为“（）（（））”。

第三张符环的长度为 $50$ ，颜色交替出现。可以证明，它不能对应任何魔法。

本题为 Beijing 2011 试题「符环」，题面与测试数据整理自 BZOJ。

3
D
SSD
SDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSDSD

1
1
0