UVA11350 Stern-Brocot Tree

数论中，Stern-Brocot 树是一种组织所有非负有理数（加上一个代表无穷的 $\frac 10$）的方法。 这棵树可以以如下迭代方式构建：首先初始化序列 $a_0=[\frac 01,\frac 10]$ 表示 $0$ 和 $\infty$。接下来的每次迭代，在相邻的两个分数间插入它们的中项（$\frac ab$ 和 $\frac cd$ 的中项是 $\frac{a+c}{b+d}$）。例如，这是初始的 $3$ 次迭代所得的序列： $$ \begin{aligned} a_0&=\left[\frac 01,\frac 10\right]\\ a_1&=\left[\frac 01,\frac 11,\frac 10\right]\\ a_2&=\left[\frac 01,\frac 12,\frac 11,\frac 21,\frac 10\right]\\ a_3&=\left[\frac 01,\frac 13,\frac 12,\frac 23,\frac 11,\frac 32,\frac 21,\frac 31,\frac 10\right]\\ \end{aligned} $$ 这个过程可以表示为一棵无限的二叉树，其中树的每一层对应着一次迭代中新加入的分数。最后得到的如下图所示的树就是 Stern-Brocot 树。  给定一个字符串，这个字符串由 `L` 和 `R` 组成。从 $\frac{1}{1}$ 开始，`L` 表示左边儿子节点，`R` 表示右边儿子节点，往下进行遍历，直到字符串结束。你需要求出这个字符串对应的分数。 比如说字符串 `RLR` ，按照步骤从 $\frac{1}{1}$ 开始往下遍历，可以得到 $\frac{1}{1}\to\frac{2}{1}\to\frac{3}{2}\to\frac{5}{3}$，所以 `RLR` 就对应着 $\frac 53$。

本题有多组数据。第一行一个整数 $N$，代表数据组数。 对于每组数据：一行一个字符串，由 `L` 和 `R` 组成，用于遍历的字符串。

对于每组数据： 一行一个分数，格式为 $a/b$ ，$a$ 为分子，$b$ 为分母，按照字符串遍历后的结果。

对于所有的数据，$0