该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$\hspace{15pt}$这是一个共轭题目，与 $J$ 题共轭！

$\hspace{15pt}$Stern-Brocot 树是一种生成所有正有理数的美丽方式。这棵树的根节点是 $1/1$.

$\hspace{15pt}$在构建过程中，我们首先在左侧放置 $0/1$，在右侧放置 $1/0$.树上的任意一个节点都可以通过其左边界 $p_1/q_1$ 和右边界 $p_2/q_2$ 计算得出，其值为 $(p_1+p_2)/(q_1+q_2)$.

$\hspace{15pt}$从根节点 $1/1$ 开始，每次向左走（标记为 $L$），当前节点就会成为新的右边界；每次向右走（标记为 $R$），当前节点就会成为新的左边界.

$\hspace{15pt}$现在，给定一个由字符 $L$ 和 $R$ 组成的字符串 $S$，代表从根节点开始在 Stern-Brocot 树上行走的路径. 请你输出路径终点所在节点对应的有理数 $p/q$.

在每一次运行中，你需要求解 $T$ 组样例.

Constraints

• $1 \leq T$
• $1 \leq |S| \leq 80$ （$|S|$ 表示字符串 $S$ 的长度）
• $|S|$ 之和不大于 $8000$

Input

$\hspace{15pt}$通过标准输入输入数据，满足以下格式：

$T \\ case_1\\ case_2\\ .\\ .\\ case_T\\$

$\hspace{15pt}$每一组测试用例满足以下格式：

$S$

Output

$\hspace{15pt}$输出共 $T$ 行，对于第 $i$ 行，你要输出 $i$ 组测试用例的答案.

$\hspace{15pt}$对于每一个测试用例，你要输出 $2$ 个数字，空格分割，分别表示 $p$, $q$.

Samples

3
LR
RLL
LLLL

2 3
4 3
1 5