Mr. Panda 最近收到了一台全新的打字机作为生日礼物。他非常喜欢这台打字机，并希望用它打出一封感谢信 $S$ 寄给 Mr. Champion。

为了打出这封感谢信，Mr. Panda 从一张白纸上的空字符串开始，可以使用打字机执行以下操作：

• 花费 $X$ 单位时间，在当前字符串末尾添加任意单个字符。
• 花费 $Y$ 单位时间，将当前字符串的任意子串（即当前字符串中某一起点到终点之间的所有连续字符）复制到剪贴板。此操作会覆盖剪贴板中原有的内容。剪贴板初始为空。
• 花费 $Z$ 单位时间，将剪贴板中的全部内容添加到当前字符串的末尾。（剪贴板的内容保持不变。）

Mr. Panda 需要使他打出的字符串与感谢信 $S$ 的内容完全一致。注意，Mr. Panda 必须精确打出这封感谢信，不能包含任何多余的字符。

Mr. Panda 希望找到一种花费时间最少的方式来打出这封感谢信。由于他太懒了，所以请求你的帮助。

你能帮 Mr. Panda 找到一种最优的打字方式，使得所花费的时间最少吗？注意，你只需要告诉 Mr. Panda 所需的最少时间单位数。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含四个整数 $n$ ($1 \le n \le 5000$)，即感谢信的长度，$X$、$Y$ 和 $Z$ ($1 \le X, Y, Z \le 10^9$)。$X$、$Y$ 和 $Z$ 分别是打字机执行各项操作的时间成本。

接下来一行包含 $n$ 个整数 $S_0, S_1, \dots, S_{n-1}$，表示感谢信的内容。每个整数 $S_i$ ($1 \le S_i \le 10^9$) 代表信中的一个字符。

保证至少 80% 的测试用例中 $n \le 1000$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是打出感谢信所需的最少时间单位数。

样例

输入 1

2
6 1 1 1
1 2 3 1 2 3
6 10 8 8
1 2 2 1 2 3

输出 1

Case #1: 5
Case #2: 56