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.
testcases = int(input())


# def total(a, b):
#     if a < 0 and b < 0:
#         a = a * (-1)
#         b = b * (-1)
#     elif a < 0:
#         b = b * (-1)
#     elif b < 0:
#         a = a * (-1)
#     return abs(a + b)


# def equalize(x, y, cost):
#     if x < y:
#         return cost * x, y - x
#     return cost * y, x - y


for _ in range(testcases):
    x, y = [int(value) for value in input().split(' ')]
    a, b = [int(value) for value in input().split(' ')]

    # if x == y == 0:
    #     print(0)
    #     continue
    
    # # If both x and y are negative numbers, convert them to positive to deal with both cases.
    # if x < 0 and y < 0:
    #     x = x * (-1)
    #     y = y * (-1)

    # # Computer the lowest and highest of values
    # low = min(a, b)
    # high = max(a, b)

    # # If the lowest and highest values are the same, it doens't matter which one you use.
    # if low == high:
    #     print(low * total(x, y))
    #     continue

    # # If the highest value
    # if high < low * 2 and high == b:
    #     cost_so_far, value_left = equalize(x, y, high)
    #     print(cost_so_far + low * value_left)
    #     # Edge case, high is not b... 555 and 391
    # else:
    #     print(low * total(x, y))
    if x == y == 0:
        print(0)
        continue
    
    val = a * abs(x-y)

    if x * y >= 0:
        val += b * min(x, y)
    
    val2 = a* (x+y)

    if x*y < 0:
        print(val)
        continue
    print(min(val, val2))
