B. Good String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar bought a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$ for Diya's birthday gift. But later he knows that Diya likes only binary strings if it doesn't contain 01 and 10 as substrings, and termed it as Good String.

To make a string good, there are two possible operations available for Yugandhar.

  1. Choose a character and flip it(change 0 to 1 and vice-versa).
  2. Choose characters from two different positions in the string, and replace these characters with their XOR value.

Operation 1 costs $$$a$$$ coins and Operation 2 costs $$$b$$$ coins. Yugandhar doesn't have too much money. So he wants to convert the given string to Good String using minimum number of coins.

Can you help Yugandhar with minimum number of coins needed to convert the string Good?

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each testcase contains three integers $$$n,a,b$$$ ($$$1 \le n,a,b \le 10^3$$$), the length of binary string, number of coins required for operation 1, number of coins required for operation 2 respectively.

The second line of each testcase contains a binary string $$$S$$$ of length $$$n$$$.

Output

For each test case, print a single integer — the minimum number of coins needed to convert the given string to Good String

Example
Input
4
2 1 1
10
3 2 1
110
4 4 2
1010
6 5 6
110011
Output
1
1
2
10
Note

In the $$$1^{st}$$$ testcase, It is optimal to convert the first character of the given string using Operation 1. So the total coins spent are $$$1$$$.