You are responsible for installing a gas pipeline along a road. Let's consider the road (for simplicity) as a segment $[0, n]$ on $OX$ axis. The road can have several crossroads, but for simplicity, we'll denote each crossroad as an interval $(x, x + 1)$ with integer $x$. So we can represent the road as a binary string consisting of $n$ characters, where character 0 means that current interval doesn't contain a crossroad, and 1 means that there is a crossroad.

Usually, we can install the pipeline along the road on height of $1$ unit with supporting pillars in each integer point (so, if we are responsible for $[0, n]$ road, we must install $n + 1$ pillars). But on crossroads we should lift the pipeline up to the height $2$, so the pipeline won't obstruct the way for cars.

We can do so inserting several zig-zag-like lines. Each zig-zag can be represented as a segment $[x, x + 1]$ with integer $x$ consisting of three parts: $0.5$ units of horizontal pipe + $1$ unit of vertical pipe + $0.5$ of horizontal. Note that if pipeline is currently on height $2$, the pillars that support it should also have length equal to $2$ units.

 [Image] 

Each unit of gas pipeline costs us $a$ bourles, and each unit of pillar — $b$ bourles. So, it's not always optimal to make the whole pipeline on the height $2$. Find the shape of the pipeline with minimum possible cost and calculate that cost.

Note that you must start and finish the pipeline on height $1$ and, also, it's guaranteed that the first and last characters of the input string are equal to 0.


-----Input-----

The fist line contains one integer $T$ ($1 \le T \le 100$) — the number of queries. Next $2 \cdot T$ lines contain independent queries — one query per two lines.

The first line contains three integers $n$, $a$, $b$ ($2 \le n \le 2 \cdot 10^5$, $1 \le a \le 10^8$, $1 \le b \le 10^8$) — the length of the road, the cost of one unit of the pipeline and the cost of one unit of the pillar, respectively.

The second line contains binary string $s$ ($|s| = n$, $s_i \in \{0, 1\}$, $s_1 = s_n = 0$) — the description of the road.

It's guaranteed that the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — one per query. For each query print the minimum possible cost of the constructed pipeline.


-----Example-----
Input
4
8 2 5
00110010
8 1 1
00110010
9 100000000 100000000
010101010
2 5 1
00

Output
94
25
2900000000
13



-----Note-----

The optimal pipeline for the first query is shown at the picture above.

The optimal pipeline for the second query is pictured below:

 [Image] 

The optimal (and the only possible) pipeline for the third query is shown below:

 [Image] 

The optimal pipeline for the fourth query is shown below:

 [Image]

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    s = input().strip()
    ans = (n + 1) * b + n * a
    
    if '1' in s:
        ans += 2 * a
        s = s[s.find('1'):s.rfind('1') + 1]
        t = [0] * (len(s) + 1)
        for i in range(len(s)):
            x = int(s[i])
            t[i] = max(t[i], x)
            t[i + 1] = max(t[i + 1], x)
        i = 0
        while i < len(t):
            j = i + 1
            while j < len(t) and t[i] == t[j]:
                j += 1
            if t[i]:
                ans += b * (j - i)
            else:
                ans += min(b * (j - i), 2 * a) 
            i = j
    
    print(ans)

from sys import stdin
t=int(stdin.readline().strip())
for Ta in range(t):
    n,a,b=list(map(int,stdin.readline().strip().split()))
    s=stdin.readline().strip()
    dp=[[10**15,10**15] for i in range(n)]
    dp[0][0]=a+b
    dp[0][1]=b+2*a
    for i in range(1,n):
        if s[i]=='0':
            dp[i][0]=min(dp[i-1][0]+a+b,dp[i-1][1]+2*a+2*b)
            dp[i][1]=min(dp[i-1][0]+b+2*a,dp[i-1][1]+2*b+a)
        else:
            dp[i][1]=dp[i-1][1]+2*b+a
    print(dp[-1][0]+b)


def mp():
    return map(int, input().split())

def f(i, j):
    return a[i][j] == a[i + 1][j] == a[i][j + 1] == a[i + 1][j + 1] == 1

q = int(input())

for qq in range(q):
    n, a, b = mp()
    s = input()
    dp_u = [0] * (n + 1)
    dp_d = [0] * (n + 1)
    dp_u[0] = 10 ** 20
    dp_d[0] = b
    
    for i in range(1, n):
        dp_u[i] = min(dp_u[i - 1] + a, dp_d[i - 1] + 2 * a) + 2 * b
        if s[i] == '0' and s[i - 1] == '0':
            dp_d[i] = min(dp_u[i - 1] + 2 * a, dp_d[i - 1] + a) + b
        else:
            dp_d[i] = 10 ** 20
    
    #print(dp_u)
    #print(dp_d)
    print(min(dp_d[n - 1] + a, dp_u[n - 1] + 2 * a) + b)

q = int(input())
for query in range(q):
    n, a, b = map(int, input().split())
    s = input()
    pod = []
    count = 1
    for i in range(1, n):
        if s[i] != s[i - 1]:
            pod.append(count)
            count = 1
        else:
            count += 1
    pod.append(count)
    wyn = n * a + 2 * n * b + 2 * b
    for i in range(len(pod)):
        if i % 2 == 0:
            if i == 0 or i == len(pod) - 1:
                wyn -= (b * pod[i]-a)
            else:
                wyn -= max(0, b * (pod[i] -1) - 2 * a)
    if len(pod) == 1:
        print((n + 1) * b + n * a)
    else:
        print(wyn)

for _ in range(int(input())):
    n, a, b = list(map(int, input().split()))
    s = input()+'0'
    min1, min2 = b, float('inf')
    for q in range(n):
        min3 = min(min1+2*a+b*2, min2+a+b*2)
        if s[q+1] == '0' and s[q] == '0':
            min1 = min(min1+a+b, min2+2*a+b)
        else:
            min1 = float('inf')
        min2 = min3
    print(min1)


T = int(input())
for i in range(T):
    n, a, b = list(map(int, input().split()))
    s = input()
    dp = [[1000000000000000001 for i in range(2)] for j in range(n+1)]
    dp[0][0] = a + 2*b
    dp[0][1] = 2*a + 3*b
    for i in range(n-1):
        if s[i] == "0":
            if s[i+1] == "1":
                dp[i+1][1] = dp[i][1] + a + 2*b
            else:
                dp[i+1][1] = min(dp[i][1] + a + 2*b, dp[i][0] + 2*a + 2*b)
                dp[i+1][0] = min(dp[i][1] + 2*a + b, dp[i][0] + a + b)
        else:
            if s[i+1] == "1":
                dp[i+1][1] = dp[i][1] + a + 2*b
            else:
                dp[i+1][1] = dp[i][1] + a + 2*b
                dp[i+1][0] = dp[i][1] + 2*a + b
    print(dp[n-1][0])


import sys
input = sys.stdin.readline

T=int(input())
for testcases in range(T):
    n,a,b=list(map(int,input().split()))
    S=list(map(int,list(input().strip())))
    S.append(0)

    ANS=(n+1)*b+n*a

    DP=[[1<<50,1<<50] for i in range(n+1)]
    DP[0][0]=0

    for i in range(1,n+1):
        if S[i-1]==S[i]==0:
            DP[i][0]=min(DP[i-1][0],DP[i-1][1]+a)
            DP[i][1]=min(DP[i-1][0]+a+b,DP[i-1][1]+b)

        else:
            DP[i][1]=min(DP[i-1][0]+a+b,DP[i-1][1]+b)

    #print(DP)

    print(ANS+DP[-1][0])
            


T = int(input())
for _ in range(T):
	n, a, b = map(int, input().split())
	s = input()
	res = 0
	i = 0
	while i < n and s[i] == '0':
		res += a + b
		i += 1
	if i < n:
		res += 2*a
		while s[n-1] == '0':
			res += a + b
			n -= 1
		res += (n-i+1)*2*b + (n-i)*a
		nz = 0
		while i < n:
			if s[i] == '1':
				if nz > 1 and 2*a-(nz-1)*b < 0:
					res += 2*a-(nz-1)*b
				nz = 0
			else:
				nz += 1
			i += 1
	else:
		res += b
	print(res)

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    s = input()
    if '1' not in s:
        print((n + 1) * b + a * n)
    else:
        cg = 0
        for i in range(len(s) - 1):
            if s[i] == '1' and s[i - 1] == '0':
                cg += 1
            if s[i] == '1':
                cg += 1
        ans = (n + 1) * b + n * a + cg * b
        c = 0
        D = []
        F = 1
        for i in s:
            if i == '0':
                c += 1
            elif F:
                ans += max(0, a)
                c = 0
                F = 0
            else:
                ans += max(0, min(2 * a, (c - 1) * b))
                c = 0
        ans += max(0, a)
        print(ans)

#E71_C

T = int(input())

for i in range(0, T):
    ln = [int(j) for j in input().split(" ")]
    n = ln[0]
    a = ln[1]
    b = ln[2]
    st = list(input())
    ct = 0
    zct = 0
    pls = 0
    pip = 0
    seg = []
    ft = False
    for j in range(0, len(st)):
        if st[j] == "1":
            ft = False
            if ct == 0:
                seg.append(j - 1)
            ct += 1
            zct = 0
        elif zct == 0 and ct:
            ct += 1
            ft = True
            zct += 1
        else:
            if ft:
                ft = False
                ct -= 1
            zct += 1
            if zct == 2 and ct:
                seg.append(j - 1)
                pls += ct + 1
                zct = 0
                ct = 0
    if zct == 1 and ct:
        seg.append(j)
        if ft:
            ct -= 1
        pls += ct + 1
    cost = pls * (b * 2) + (n + 1 - pls) * (b)
    cost += (n + len(seg)) * a
    if len(seg) > 2:
        for j in range(1, len(seg) - 1,2):
            plc = (seg[j + 1] - seg[j]) * b
            pipc = 2 * a
            if plc < pipc:
                cost -= (pipc - plc)
    print(cost)


import sys
def input():
	return sys.stdin.readline()[:-1]

t = int(input())
ans = []
for _ in range(t):
	n, a, b = map(int, input().split())
	s = input()
	res = [b, 10**30]
	for i in range(n):
		tmp = []
		if s[i] == "0":
			tmp.append(min(res[0]+a+b, res[1]+2*a+b))
			tmp.append(min(res[1]+a+2*b, res[0]+2*a+2*b))
		else:
			tmp.append(10**30)
			tmp.append(res[1]+a+2*b)
		res = tmp
	ans.append(res[0])
print(*ans, sep="\n")

def mi():
        return list(map(int, input().split()))
'''
4
8 2 5
00110010
8 1 1
00110010
9 100000000 100000000
010101010
2 5 1
00
'''
for _ in range(int(input())):
    n,a,b = mi()
    s = list(map(int, input()))
    ans = (a+b)*n+b
    if 1 not in s:
        print (ans)
        continue
    i1 = s.index(1)
    i2 = n-1-s[::-1].index(1)
    ans+= 2*a + (i2-i1+2)*b
    i = i1
    while i<i2:
        enter = False
        while i<i2 and s[i]==1:
            enter = True
            i+=1
        start = i
        while i<i2 and s[i]==0:
            enter = True
            i+=1
        if i<n and s[i]==1 and s[i-1]==0:
            enter = True
            if 2*a-b*(i-start-1)<0:
                ans+=2*a-b*(i-start-1)
        if not enter:
            break
    print (ans)


def main():
    import sys
    input = sys.stdin.readline
    
    def solve():
        n, a, b = map(int, input().split())
        s = input()
        
        arr = [0] * (n + 1)
        for i in range(1, n):
            if s[i] == '1' or s[i - 1] == '1':
                arr[i] = 1
        
        cnts = []
        cnt = 1
        for i in range(1, n + 1):
            if arr[i] != arr[i - 1]:
                cnts.append(cnt)
                cnt = 1
            else:
                cnt += 1
        cnts.append(cnt)
        
        l = len(cnts)
        cost = n * a + (l - 1) * a + (n + 1) * b + sum(cnts[1:l:2]) * b
        for i in range(2, l - 2, 2):
            now = 2 * a + cnts[i] * b
            new = cnts[i] * 2 * b
            if new < now:
                cost += new - now
        
        print(cost)
    
    for _ in range(int(input())):
        solve()
    
    return 0

main()

for _ in range(int(input())):
    n, a, b = list(map(int, input().split()))
    s = input()
    if s == "0" * n:
        print(a * n + b * n + b)
        continue
    ans = 0
    ind = 0
    ind2 = n - 1
    pref = 0
    suf = 0
    while ind2 >= 0 and s[ind2] == "0":
        ind2 -= 1
        suf += 1
    while ind < n and s[ind] == "0":
        ind += 1
        pref += 1
    while ind <= ind2:
        if s[ind] == "0":
            size = 0
            while ind <= ind2 and s[ind] == "0":
                ind+=1
                size += 1
            ans += min((size - 1) * b + size * a + 2 * a, size * a + 2 * b * (size - 1))
        else:
            size = 0
            while ind <= ind2 and s[ind] == "1":
                ind+=1
                size += 1
            ans += (size + 1) * b * 2 + size * a
    ans += pref * b + pref * a + a
    ans += suf * b + suf * a + a
    print(ans)

t = int(input())
for i in range(t):
    n, a, b = list(map(int, input().split()))
    s = input()
    arr = []
    c = "0"
    k = 0
    for i in range(n):
        if s[i] == c:
            k += 1
        else:
            arr.append(k)
            k = 1
            c = s[i]
    if len(arr) == 0:
        print(n * a + b * n + b)
    else:
        ans = k * (a + b) + (a + b) * arr[0] + a
        for i in range(1, len(arr)):
            if i % 2 == 1:
                ans += (arr[i] + 1) * (2 * b + a)
            else:
                ans += min((arr[i] + 1) * a + b * (arr[i] - 1), 2 * b * (arr[i] - 1) + a * (arr[i] - 1))
        print(ans)
                    


t = int(input())
for _ in range(t):
    n,pipeCost,pillarCost = map(int,input().split())
    road = input()
    cost = 0

    # get consequtive frequence, guranteed to start and end with one
    freq = []
    curr = "0"
    currFreq = 0
    for i in road:
        if i == curr:
            currFreq += 1
        else:
            freq.append(currFreq)
            curr = i
            currFreq = 1
    freq.append(currFreq)

    # If only a single sequence of 1's
    if len(freq) == 3:
        cost += pillarCost*freq[0]
        cost += pillarCost*2*(freq[1]+1)
        cost += pillarCost*freq[2]
        cost += pipeCost*(sum(freq)+2)

    elif len(freq) == 1:
        cost += pillarCost*(freq[0]+1)
        cost += pipeCost*(freq[0])

    else:
        # represents ground level
        level = True
        switch = 0

        cost += pipeCost*(sum(freq))
        for i in range(len(freq)):
            # zero at 0,2,4...
            if i%2 == 0:
                if level:
                    if i==0 or i==len(freq)-1:
                        cost += pillarCost*freq[i]
                    else:
                        cost += pillarCost*(freq[i]-1)
                else:
                    if i == len(freq)-1:
                        level = True
                        cost += pillarCost*freq[i]
                    else:
                        if (freq[i]-1)*pillarCost > 2*pipeCost:
                            level = True
                            cost += pillarCost*(freq[i]-1)
                        else:
                            cost += pillarCost*2*(freq[i]-1)
            else:
                if level:
                    level = False
                    switch += 1
                    cost += pillarCost*2*(freq[i]+1)
                else:
                    cost += pillarCost*2*(freq[i]+1)
        
        cost += 2*switch*pipeCost
    
    print(cost)

T = int(input())
for _ in range(T):
    n, a, b = map(int, input().split())
    s = list(map(int, input()))
    if 1 not in s:
        print(a*n + b*(n+1))
        continue
    min_lower_length = 2*a/b + 1
    start = 0
    while s[start] == 0:
        start += 1
    end = n-1
    while s[end] == 0:
        end -= 1
    cost = (n+2)*a + (n+1)*b + (end-start+2)*b
    c = 0
    for i in range(start, end+1):
        if s[i] == 0:
            c += 1
        else:
            if c>=min_lower_length:
                cost += 2*a - (c-1)*b
            c = 0
    print(cost)

s = lambda: list(map(int, input().split()))

T = int(input())
for tc in range(T):
    n, a, b = s()
    string = list(map(lambda x: x == '1', input()))
    cost = a*n + b*(n+1)
    isBeginning = True
    # state machine
    zeros = 0
    for x in string:
        if x:
            if zeros==0:
                cost+=b
            else:
                if not isBeginning and b*(zeros-1) < 2*a:
                    cost -= 2*a
                    cost += b*(zeros-1)
                isBeginning=False
                zeros=0
                cost+=a+b
        else:
            if zeros==0:
                cost+=a+b
            zeros+=1
    print(cost-a-b) # first number

import sys

T = int(sys.stdin.readline())
for t in range (0, T):
    n, a, b = list(map(int, sys.stdin.readline().strip().split()))
    s = sys.stdin.readline().strip()
    i = 0
    c = n * a + (n + 1) * b
    v = 0
    for j in range (0, n-1):
        if s[j] == "1" or s[j+1] == "1":
            c = c + b
            v = 1
    if v == 1:
        c = c + 2 * a
        while s[i] == "0":
            i = i + 1
        j = n - 1
        while s[j] == "0":
            j = j - 1
        v = 0
        while i <= j:
            if s[i] == "1":
                if v > 0:
                    c = c + min([(v-1) * b, 2 * a])
                v = 0
            if s[i] == "0":
                v = v + 1
            i = i + 1
    print(c)

            


import sys

def solve(A, n, a, b):    
    cost = n*a + (n+1)*b
    num_ones = 0
    groups_ones = 0
    groups_zeros = [0]
    on_zeros = True
    for i in A:
        if i == 0:
            if on_zeros:
                groups_zeros[-1] += 1
            else:
                on_zeros = True
                groups_zeros.append(1)
        else:
            if on_zeros:
                on_zeros = False
                groups_ones += 1
            num_ones += 1
    cost += (groups_ones+num_ones)*b
    for i in range(1, len(groups_zeros)-1):
        z = groups_zeros[i]
        cost += min(2*a, (z-1)*b)
    if num_ones >0 :
        cost += 2*a
    return cost
           
           

in_file = sys.stdin#open("C.txt", "r") 

t = int(in_file.readline().strip())
for _ in range(t):
    n, a, b = map(int, in_file.readline().strip().split())
    A = list(map(int, in_file.readline().strip()))
    sys.stdout.write(str(solve(A, n, a, b)) + "\n")
sys.stdout.flush() 

test = int(input())
for _ in range(test):
    n,a,b = map(int,input().split())
    s = input()
    ans = a*n+b*(n+1)
    for i in range(n):
        if s[n-i-1]=='1':
            s=s[:n-i]
            break
    for i in range(len(s)):
        if s[i]=='1':
            s=s[i:]
            break
    if s.count('1')==0:
        print(ans)
        continue
    dp = []
    c = 1
    for i in range(len(s)-1):
        if s[i+1]==s[i]:
            c+=1
        else:
            dp.append(c)
            c=1
    dp.append(c)
    for i in dp[::2]:
        ans += (i+1)*b
    ans+=len(dp[::2])*a*2
    for i in dp[1::2]:
        if (i-1)*b<2*a:
            ans += (i-1)*b
            ans-=2*a
    print(ans)

t=int(input())
for i in range(t):
    n,a,b=[int(x) for x in input().split()]
    s=[int(x) for x in list(input())]
    gas=n
    h=n+1
    index=-1
    one=-1
    for i in range(n):
        if s[i]==0:
            if index!=-1:
                h+=i-index+1
                gas+=2
                index=-1
                one=i-1
        else:
            if index==-1:
                index=i
                if one!=-1 and 2*a>(i-one-2)*b:
                    gas-=2
                    h+=i-one-2
    print(gas*a+h*b)

                
    
        


import sys 
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()

for t in range(int(input())):
  n, a, b = list(map(int, input().split()))
  s = input()
  arr = [['0', 1]]
  for i in range(1, n):
    if s[i] == arr[-1][0]:
      arr[-1][1] += 1
    else:
      arr.append([s[i], 1])
  
  if len(arr) == 1:
    pipe = n
    pillar = n + 1
  else:
    pipe = n + 2
    pillar = arr[0][1] + arr[-1][1] + 2 * (n + 1 - arr[0][1] - arr[-1][1])
    for i, j in arr[1:-1]:
      if i == '0' and j >= 2 and (j-1)*b > 2*a:
        pipe += 2
        pillar -= j-1
        
  print(pipe*a + pillar*b)



      

      
        



T = int(input())
for _ in range(T):
    n, a, b = list(map( int, input().split() ))
    s = input()
    ans = n * a + ( n + 1 ) * b
    li = s.find('1')
    if li >= 0:
        ri = s.rfind('1')
        ans += a + a + ( ri - li + 2 ) * b
        lens = []
        for i in range( li + 1, ri ):
            if s[ i ] == '0':
                if( s[ i - 1 ] == '1' ):
                    lens.append(0)
                lens[-1] += 1
        for l in lens:
            sm = a + a - ( l - 1 ) * b
            if l > 1 and sm < 0:
                ans += sm
    print( ans )



def main():
    def solve():
        n,a,b = map(int,input().split())
        ss = input()
        cost = 0
        for i in range(n):
            if ss[i] == '1':
                last = i
                cost += a*(i+1)+b*i
                break
        else:
            print(a*n+b*(n+1))
            return
        for i in range(last, n):
            if ss[i] == '1' or ss[i-1] == '1':
                high = (i-last) * (a+2*b)
                low = (i-last) * (a + b) + a*2 + b
                cost += min(high, low)
                last = i
        cost += (n+1-last) * (a+b) +b
        print(cost)


    q = int(input())
    for _ in range(q):
        solve()


def __starting_point():
    main()
__starting_point()