You are given two integers x and y. You can perform two types of operations: 

  1. Pay a dollars and increase or decrease any of these integers by 1. For example, if x = 0 and y = 7 there are four possible outcomes after this operation: 
    * x = 0, y = 6; 
    * x = 0, y = 8; 
    * x = -1, y = 7; 
    * x = 1, y = 7. 

  2. Pay b dollars and increase or decrease both integers by 1. For example, if x = 0 and y = 7 there are two possible outcomes after this operation: 
    * x = -1, y = 6; 
    * x = 1, y = 8. 



Your goal is to make both given integers equal zero simultaneously, i.e. x = y = 0. There are no other requirements. In particular, it is possible to move from x=1, y=0 to x=y=0.

Calculate the minimum amount of dollars you have to spend on it.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of testcases.

The first line of each test case contains two integers x and y (0 ≤ x, y ≤ 10^9).

The second line of each test case contains two integers a and b (1 ≤ a, b ≤ 10^9).

Output

For each test case print one integer — the minimum amount of dollars you have to spend.

Example

Input


2
1 3
391 555
0 0
9 4


Output


1337
0

Note

In the first test case you can perform the following sequence of operations: first, second, first. This way you spend 391 + 555 + 391 = 1337 dollars.

In the second test case both integers are equal to zero initially, so you dont' have to spend money.
inp = input()
num_cases = int(inp)

for _ in range(num_cases):
    x, y = list(map(lambda x: int(x), input().split(' ')))
    a, b = list(map(lambda x: int(x), input().split(' ')))

    T = 0

    while not (x == y == 0):
        closer_amt = lambda d, e: (abs(x) - abs(x + d)) + \
                (abs(y) - abs(y + e))

        cost       = lambda op: a if op[0] == 'a' else b
        # As
        op1 = cost('a'), -1, 0  ,closer_amt(-1, 0)  
        op2 = cost('a'), 0, -1  ,closer_amt(0, -1)  
        op3 = cost('a'), 1, 0   ,closer_amt(1, 0)   
        op4 = cost('a'), 0, 1   ,closer_amt(0, 1)   
        # Bs                    
        op5 = cost('b'), -1, -1, closer_amt(- 1, -1)
        op6 = cost('b'), 1, 1   ,closer_amt(1, 1)   

        # Decide
        options = list(filter(lambda op: op[3] > 0, [op1,op2,op3,op4,op5, op6]))
        option = min(options, key=lambda op: op[0] / op[3])
        # Can we do the operation multiple times?
        xm, ym = option[1:3]
        amount = 1
        last_closer = closer_amt(amount * xm, amount * ym)
        if xm == 0:
            amount = abs(y) - 1
        elif ym == 0:
            amount = abs(x) - 1
        else:
            amount = min(abs(x) , abs(y))
        while True:
            this_closer = closer_amt((amount + 1) * xm, (amount + 1) * ym)

            if this_closer < last_closer or \
                    (x != 0 and (x + (xm * amount)) == 0) or \
                    (y != 0 and (y + (ym * amount)) == 0):
                break
            last_closer = this_closer
            amount += 1

        x = x + (xm * amount)
        y = y + (ym * amount)
        T += option[0] * amount

        

    print(T)


