You are given 2 strings A and B of the same length N. A contains '0', '1', and '?'; B contains only '0' and '1'. Your task is to find minimum cost of transforming A into B by performing sequence of allowed operations with string A. Following operations are allowed:
Change '0' to '1' with cost x
Change '1' to '0' with cost y
Change '?' to either '0' or '1' with cost z
Swap two adjacent characters with cost t.

Note that you are not allowed to apply these operations in B.

Input

The first line contains T - the number of test cases. Then T test cases follow.

Each test case consists of several lines.
The first line contains 5 positive integers N, x, y, z and t.
The second line contains string A.
The third line contains target string B.

Output

For each test, print the minimum cost in one line.

Constraints
Let SN be the sum of N over all T test cases
1 ≤ SN ≤ 2000
1 ≤ x, y, z, t ≤ 1000
z ≤ min(x, y)
30% of tests in which SN ≤ 25

SAMPLE INPUT
3
6 1 1000 1 1
01??00
001010
2 1 1 1 1
01
10
5 1 1 1 2
00000
10000

SAMPLE OUTPUT
4
1
1

见题面

见题面