你最近对你的上级长官搞了一个绝妙的恶作剧。这非常成功——你被迅速降职，解除了职务，并被指派去指挥一支由精心挑选的士兵组成的精英排，即著名的“半吊子”（Halfwitters）。据说，没有一个“半吊子”曾被敌人收买或在战斗中丢脸——他们根本不懂撤退或背叛的概念。而且，没有一个“半吊子”曾在室外温度可能低于其智商的地方服役。

这个由 $n$ 名士兵组成的排正排成一列站在你面前。你希望士兵们按从最高（编号 1）到最矮（编号 $n$）的顺序站立。然而，这一点还没向排里解释清楚。现在，他们正按照他们最喜欢的“谁先吃完甜点谁就排前面”的顺序站着。你可以采取以下三种行动：

• 告诉任意两名相邻的士兵交换位置。这需要花费 $a$ 分钟来解释。
• 命令整个排反转队列的顺序——这是一个高难度动作，但他们已经演练过了，需要 $b$ 分钟来提醒。
• 发脾气并大喊大叫 $c$ 分钟。这会造成极大的恐慌和混乱，在大喊大叫结束后，士兵们会随机重新排列成一个完全随机的顺序。

假设采取最优策略，达到期望的顺序 $(1, 2, \dots, n)$ 所需的期望时间是多少？你将对该排进行 $d$ 天的训练，每天开始时由于甜点的不同，士兵的初始顺序可能不同。请计算每一天的答案。

输入格式

输入的第一行包含测试用例的数量 $z$。接下来是各测试用例的描述。

每个测试用例的第一行包含五个整数 $n, a, b, c, d$ ($2 \le n \le 16, 1 \le a, b, c \le 1000, 1 \le d \le 10\,000$)，分别表示士兵人数、各项行动的代价以及天数。接下来的 $d$ 行，每行包含一个序列 $(1, 2, \dots, n)$ 的排列，表示连续几天中士兵的初始顺序。所有测试用例中的总天数不超过 $100\,000$。

输出格式

对于每个测试用例，输出 $d$ 行——对于每一天，输出整理士兵所需的时间期望值。由于这是一个有理数，请将其表示为不可约分数 $p/q$ 的形式。

样例

样例输入 1

1
6 1 1 1 3
1 2 3 4 5 6
5 4 3 2 1 6
6 4 2 1 3 5

样例输出 1

0/1
6/1
2771/428