Minimum Cost to Transform a String into a Palindrome

You are given a string \(S\) and two integers \(X\) and \(Y\) which represent the cost of swapping any two characters and the cost of replacing any character, respectively. Your task is to compute the minimum cost required to transform \(S\) into a palindrome.

A palindrome is a string that reads the same forwards and backwards. For every pair of characters \(S[i]\) and \(S[n-i-1]\) that do not match (where \(n\) is the length of the string), you can either swap them at a cost of \(X\) or replace one of them at a cost of \(Y\). For each such mismatched pair, the optimal cost is \(\min(X, Y)\).

Note: The length of \(S\) is provided explicitly as \(K\) and it is guaranteed that \(K = |S|\). Consider each test case independently.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer \(T\) representing the number of test cases.
2. For each test case:
   • The first line contains an integer \(K\) denoting the length of the string \(S\).
   • The second line contains the string \(S\).
   • The third line contains two space-separated integers \(X\) and \(Y\), where \(X\) is the cost of swapping any two characters and \(Y\) is the cost of replacing any character.

outputFormat

For each test case, output a single line to stdout containing the minimum cost required to transform \(S\) into a palindrome.

## sample

1
3
abc
5 3

3

</p>