Dasha has (10^{100}) coins. Recently, she found a binary string (s) of length (n) and some operations that allows to change this string (she can do each operation any number of times): Replace substring 00 of (s) by 0 and receive (a) coins. Replace substring 11 of (s) by 1 and receive (b) coins. Remove 0 from any position in (s) and pay (c) coins. It turned out that while doing this operations Dasha should follow the rule: It is forbidden to do two operations with the same parity in a row. Operations are numbered by integers (1)-(3) in the order they are given above. Please, calculate what is the maximum profit Dasha can get by doing these operations and following this rule. The first line contains a single integer (t) ((1 \leq t \leq 10^4)) — the number of test cases. The first line of each test case contains four integers (n), (a), (b), (c) ((1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9)). The second line of each test case contains a binary string (s) of length (n). It is guaranteed that the total sum of (n) over all test cases doesn't exceed (2 \cdot 10^5). For each test case print the answer. In the first test case one of the optimal sequences of operations is 0 11 01 (\rightarrow) 01 0 1 (\rightarrow) 0 11 (\rightarrow) 01 . This sequence of operations consists of operations (2), (3) and (2) in this order. It satisfies all rules and gives profit (3). It can be shown that it is impossible to achieve higher profit in this test case, so the answer is (3). In the second test case one of the optimal sequences of operations is 110 00 1 (\rightarrow) 11 001 (\rightarrow) 1 00 1 (\rightarrow) 101 . In the third test case one of the optimal sequences of operations is 01 11 10 (\rightarrow) 0 1110 (\rightarrow) 11 10 (\rightarrow) 11 0 (\rightarrow) 11 (\rightarrow) 1 .