这个问题关于随机字符串。设随机字符串生成器 (RSG) 是一个生成由字符 A 和 B 组成的字符串的程序。字符串生成过程分为两步。

第一步，生成生成器。从集合 $\{1, 2, \dots, 10\}$ 中等概率选择一个参数 $k$。该参数是生成下一个字符所需的后缀长度。

之后，选择 $2^k$ 个参数。这些参数是对于所有由 $\{A, B\}$ 组成的长度为 $k$ 的字符串 $s$ 的 $p_s^A$。参数 $p_s^A$ 在区间 $[0, 1]$ 上独立且均匀地选择（这意味着对于每个 $t \in [0, 1]$， $p_s^A < t$ 的概率等于 $t$）。这些参数是后缀 $s$ 之后出现字符 A 的概率。

第二步，我们使用该生成器生成一个无限长的字符串。字符串的前 $k$ 个字符是独立且均匀选择的（每个字符为 A 的概率为 $\frac{1}{2}$）。

之后每个字符仅取决于前 $k$ 个字符组成的长度为 $k$ 的后缀 $s$。下一个字符为 A 的概率为 $p_s^A$，为 B 的概率为 $p_s^B = 1 - p_s^A$。

给定由上述两步过程生成的字符串的前几个字符（注意给出的字符数可能小于 $k$）。你需要输出该字符串的下一个字符为 A 的概率。保证给定前缀生成的概率严格大于零。

输入格式

输入的第一行包含一个整数 $T$ —— 测试用例的数量 ($1 \le T \le 10\,000$)。接下来的 $T$ 行，每行包含一个测试用例 —— 一个仅由字符 A 和 B 组成的非空字符串。所有测试用例均由上述两步过程独立生成（在每个测试用例中，生成器和无限字符串与其他测试用例分开生成）。所有 $T$ 个字符串的长度之和不超过 $10\,000$ 个字符。

输出格式

对于每个测试用例，输出所需的概率，要求绝对误差或相对误差不超过 $10^{-6}$。

样例

输入 1

4
A
BB
AAA
ABA

输出 1

0.5
0.4833333333333334
0.5483870967741935
0.4833333333333334