玩具排序

题目描述

奶龙最近在学习如何整理他的玩具。他有 $T$ 组玩具排列，每组排列有 $n$ 个玩具，编号从 $1$ 到 $n$。奶龙希望通过以下三种操作将玩具排列整理成从小到大的顺序：

1. 交换相邻玩具：奶龙可以选择两个相邻的玩具，交换它们的位置。每次交换需要花费 $a$ 时间。
2. 翻转整个排列：奶龙可以将整个玩具排列翻转过来。每次翻转需要花费 $b$ 时间。
3. 随机重排：奶龙可以将玩具排列随机打乱，打乱后的排列是所有可能的排列中的一种，每种排列出现的概率相同。每次随机重排需要花费 $c$ 时间。

奶龙想知道，通过这三种操作，将玩具排列整理成编号递增顺序的最小期望耗时是多少。答案需要用最简分数表示。

输入格式

第一行输入一个正整数 $T$，表示奶龙有多少组玩具排列需要整理。

对于接下来的每一组数据，第一行输入四个正整数 $n, a, b, c$，分别表示玩具的数量和三种操作的耗时。

第二行输入一个长度为 $n$ 的排列，表示奶龙当前的玩具排列。

输出格式

输出 $T$ 行，每行输出一个形如 $A/B$ 的最简分数，表示奶龙整理这组玩具排列的最小期望耗时。

注意：可以分子大于分母，但是分数必须是最简形式，即分子和分母不能有大于 $1$ 的公因数。即使分母为 $1$，也要保留分母。

样例 #1

样例输入 #1

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

样例输出 #1

0/1
377/71
9/1

提示

本题共有 $10$ 组数据。

对于第 $1$ ~ $7$ 组数据，第 $i$ 组数据 $n \le 2i$。

对于第 $1, 3, 5, 7, 9$ 组数据，奶龙只有一组玩具排列需要整理，即 $T=1$。

对于所有数据，满足 $1 \le T \le 10^4$，$2 \le n \le 15$，$1 \le a, b, c \le 100$。

奶龙希望通过这些操作，用最少的时间将玩具排列整理好。你能帮助他吗？