有一场考试包含 $Q$ 道是非题。每道题的正确答案要么是 $\texttt{T}$，要么是 $\texttt{F}$。每位参加考试的学生对每道题都选择 $\texttt{T}$ 或 $\texttt{F}$，学生的得分即为他们答对的题目数量。

现有 $N$ 名学生已经参加了这场考试。对于每位学生，你已知他们对每道题的回答以及他们的最终得分。假设任何与所有这些学生的得分相一致的答案序列，其成为正确答案序列的概率均相等，你希望最大化你自己的期望得分。请确定该期望得分是多少，以及如何回答这些问题以达到该得分。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$：分别表示学生人数和题目数量。接下来的 $N$ 行中，每行包含一个字符串 $A_i$ 和一个整数 $S_i$：分别表示第 $i$ 位学生的回答和他们的得分。$A_i$ 的第 $j$ 个字符为 $\texttt{T}$ 或 $\texttt{F}$，表示第 $i$ 位学生对第 $j$ 道题的回答。

输出格式

对于每个测试用例，输出一行 Case #x: y z/w，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个字符串，表示能获得最大期望得分的答案序列（格式与输入相同），$z/w$ 是最大期望得分，表示为不可约分数（即 $w$ 必须为正数且尽可能小）。

数据范围

$1 \le T \le 2021$。 $0 \le S_i \le Q$，对于所有 $i$。 输入保证至少存在一个与输入一致的正确答案序列。

测试集 1（可见判定） $1 \le N \le 2$。 $1 \le Q \le 10$。

测试集 2（隐藏判定） $1 \le N \le 2$。 $1 \le Q \le 40$。

测试集 3（隐藏判定） $1 \le N \le 3$。 $1 \le Q \le 120$。

样例

样例输入 1

4
1 3
FFT 3
1 3
FFT 2
2 6
FFTTTF 2
FTFTFT 4
2 2
FF 1
TT 1

样例输出 1

Case #1: FFT 3/1
Case #2: FFT 2/1
Case #3: FTFFFT 4/1
Case #4: TF 1/1

说明

在样例 1 中，已知 $\texttt{FFT}$ 的得分为 3，因此正确答案序列必须是 $\texttt{FFT}$。

在样例 2 中，已知 $\texttt{FFT}$ 的得分为 2，正确答案序列可能是 $\texttt{FFF}$、$\texttt{FTT}$ 或 $\texttt{TFT}$，每种情况的概率均为 $1/3$。你的最佳策略是回答 $\texttt{FFT}$，以获得期望得分 $1/3 \times 2 + 1/3 \times 2 + 1/3 \times 2 = 2$。

在样例 3 中，还有其他答案也能达到 4 的期望得分，例如 $\texttt{FTFTFT}$。

在样例 4 中，其中一道题的答案是 $\texttt{T}$，另一道是 $\texttt{F}$，但你不知道哪道是哪道。回答 $\texttt{TF}$ 或 $\texttt{FT}$ 的得分概率各为 $1/2$ 和 $0$，产生的期望得分为 1。回答 $\texttt{FF}$ 或 $\texttt{TT}$ 则保证得分为 1。由于任何答案序列都能得到相同的期望得分，你可以输出其中任意一个。

附加样例 - 测试集 3

以下附加样例符合测试集 3 的范围。它不会在提交的解决方案中运行。

样例输入 2

1
3 120
FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFF
55
FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTT
62
FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFT
64

样例输出 2

Case #1:
FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTT
189154508532118369075350624633/2

在测试集 3 的样例中，你可以获得超过 65 的期望得分，这比其他任何学生的实际得分都要高。注意，期望得分的分子和分母都可能显著大于 $2^{64}$（本例中的分子实际上超过了 $2^{97}$）。