Ania 和 Tomek 最近坠入了爱河。他们一直在给对方发短信。我们可以假设每条短信都是一个二进制序列。Tomek 的父亲 Maksymilian 对这整件事并不太热心。他决定截获其中一条情侣短信，并将其修改为他期望的短信，这两条短信的长度相同。他必须尽可能快地完成这件事，因为他不想引起不必要的注意。

Maksymilian 可以进行以下三种操作：

1. 将某个位置上的 0 变为 1；
2. 将某个位置上的 1 变为 0；
3. 交换两个相邻位置上的比特。

每种操作都需要花费一些时间。第一种操作需要 $t_0$ 秒，第二种需要 $t_1$ 秒，第三种需要 $t_s$ 秒。父亲可以多次（可能为零次）使用任何操作，并希望尽可能快地将给定的短信修改为期望的短信。请帮帮他！

输入格式

第一行包含一个整数 $Z \le 20$，表示接下来描述的测试用例数量。

为了压缩输入的大小，所有的二进制序列都被转换成了十六进制序列，因此你可以假设每个二进制序列的长度都是 4 的倍数。

每个测试用例的第一行包含四个自然数 $n, t_0, t_1, t_s$，分别表示十六进制序列的长度以及题目描述中所述的时间。

第二行包含父亲截获的短信，第三行包含父亲想要修改成的短信。这些序列仅由集合 $\{0, 1, \dots, 9, \text{A}, \text{B}, \dots, \text{F}\}$ 中的字符组成。

$n \in [1, 10^6], t_0, t_1, t_s \in [1, 10^{12}]$

输出格式

对于每个测试用例，输出一行，包含一个整数，表示将第一个序列修改为第二个序列所需的最少秒数。

样例

输入 1

2
2 1 2 3
F0
D5
3 1 1 1
201
110

输出 1

4
3

说明

在第一个样例中，解码后的二进制序列分别为 11110000 和 11010101。