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:

1. Change '0' to '1' with cost x
2. Change '1' to '0' with cost y
3. Change '?' to either '0' or '1' with cost z
4. 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