题目描述

“静、思、定。在做重要的决定之前先冷静下来，在脑子里仔细思考一下，再决定什么是正确答案。” 柊一飒老师用生命给学生上了最后一课，那么，现在就让我们开始一场游戏思考，“Let's think"。

游戏规则如下：

每一个回合，游戏双方能从以下三种技能选择一种进行操作。

• 【集】：积攒一点能量。

• 【波】：消耗一点能量，发送一个攻击波。如果此时没有能量，则无法发动技能。如果双方都选择发动攻击波，则攻击抵消。

• 【挡】：格挡此次冲击波。

双方初始能量均为 $0$ ，

你将和笨笨铧玩 $n$ 个回合，假设现在你已经知道他 $n$ 个回合的操作了，现在你想在第 $n$ 个回合一招致命。

问：你有多少种方案，在前 $n - 1$ 回合都不使用【波】技能，并且在第 $n$ 个回合使用技能击败笨笨铧。

输入格式

第一行一个正整数 $T$（$1\le T \le 100$），代表测试样例的组数。

对于每个测试样例：

第一行输入一个正整数 $n$（$1\le n\le 60$），表示这个游戏会进行 $n$ 个回合。

第二行输入一个长度为 $n$ 的字符串，表示笨笨铧这 $n$ 个回合进行的操作。

如果是【集】的话，用【$\text{J}$】表示。

如果是【波】的话，用【$\text{B}$】表示。

如果是【挡】的话，用【$\text{D}$】表示。

笨笨铧保证题目输入合法。

输出格式

对于每一个样例：

输出一行，包含一个整数，表示你有多少种方案在 $n - 1$ 回合前不使用【波】，并且在第 $n$ 回合出其不意使用【波】技能击败笨笨铧。

输入样例

3
2
JJ
3
JJJ
3
JDB

输出样例

1
3
0

提示

第一个测试用例：你有一种方案能恰好在第 $n$ 回合击败笨笨铧：$\text{JB}$。

第二个测试用例：你有三种方案能恰好在第 $n$ 回合击败笨笨铧：$\text{JJB},\text{JDB},\text{DJB}$。

第三个测试用例：你没有任何一种方案能恰好在第 $n$ 回合击败笨笨铧。