D. 狼群之中
时间限制：每个测试 $2$ 秒
内存限制：$512$ MB

在你最近开始玩的一个游戏里，有一片可以表示为矩形网格的区域。该区域有 $2$ 行和 $n$ 列 —— 总共 $2n$ 个格子。

有些格子是空的，但有些被狼占据。游戏开始时，你有一只羊位于某个格子，你想保护它免受狼的侵害。

狼会在夜里攻击你，所以你还有一些时间进行准备。你有两种方法来对付狼：

• 你向猎人支付 $h$ 枚金币，并选择一个被狼占据的格子。猎人会清理该格子，消灭里面的狼。
• 你向建造者支付 $b$ 枚金币，并选择一个空格子。建造者会在所选格子挖一条壕沟，狼无法穿越壕沟。

你可以以任意顺序使用上述两种方法任意次数。

如果存在一条从狼的格子出发、到达羊的格子的路径，我们就说这只狼能到达羊。这条路径不能包含任何有壕沟的格子，并且路径中相邻的两个格子必须相邻（共用一条边）。

为了确保没有任何狼能到达羊，你需要支付的最小金币总数是多少？

输入
第一行包含一个整数 $t$ ($1 \le t \le 1200$) —— 测试用例的数量。接下来是 $t$ 个独立的测试用例。

每个测试用例的第一行包含三个整数 $n$, $h$ 和 $b$ ($2 \le n \le 2 \cdot 10^5$; $1 \le h, b \le 10^9$) —— 网格的大小以及相应的花费。

接下来的两行是对网格的描述。第 $i$ 行的第 $j$ 个字符是 '.'、'S' 或 'W' 之一：

• '.' 表示该格子为空；
• 'S' 表示该格子被羊占据；网格中有且仅有一个这样的格子；
• 'W' 表示该格子被狼占据。

附加限制：

• 与羊所在格子相邻的格子中没有狼；
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出一个整数 —— 拯救你的羊需要支付的最小金币总数。

示例
输入