Bertown 是一座拥有 $$$n$$$ 建筑物呈直线的城市。
该市安全部门发现一些建筑物被埋有地雷。编译了一张地图,它是一个长度为 $$$n$$$ 的字符串,其中如果建筑物号 $$$i$$$ 下有地雷,则第 $$$i$$$ 个字符为“1”,否则为“0”。
Bertown 最好的工兵知道如何激活地雷,这样上方的建筑物就不会被损坏。当编号为 $$$x$$$ 的建筑物下的地雷被激活时,它会爆炸并激活编号为 $$$x-1$$$ 和 $$$x+1$$$ 的建筑物下的两个相邻地雷(如果建筑物下没有地雷,则不会发生任何情况)。因此,激活一段连续地雷上的任意一个地雷就足以激活该段上的所有地雷。对于手动激活一个地雷,工兵需要 $$$a$$$ 硬币。他可以根据需要多次重复此操作。
此外,如果建筑物不存在,工兵可以在建筑物下面放置地雷。对于这样的操作,他需要 $$$b$$$ 硬币。他还可以根据需要多次重复此操作。
工兵可以按任意顺序执行操作。
你想炸毁城市中所有的地雷以确保安全。求工兵必须支付的最少硬币数量,以便在他的行动之后城市中不再有地雷。
输入
第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例都以包含两个整数 $$$a$$$ 和 $$$b$$$ 的行开始($$$1 \le a, b \le 1000$$$)——分别是激活和放置一个地雷的成本。
下一行包含城市中的地雷地图 - 一个由 0 和 1 组成的字符串。
所有测试用例的字符串长度总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数——工兵必须支付的最小硬币数量。
示例
输入 #1
2 1 1 01000010 5 1 01101110
输出 #1
2 6
注意
在第二个测试用例中,如果我们在第四个建筑物下放置一个地雷然后激活它,那么场上的所有地雷都会被激活。此类操作的成本为 6,$$$b=1$$$ 硬币用于放置地雷,$$$a=5$$$ 硬币用于激活。