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


while t > 0 :

    k1,k2 = input().split()
    k1 = int(k1)
    k2 = int(k2)

    m1,m2 = input().split()
    m1 = int(m1)
    m2 = int(m2)

    sum1 = 0
    sum2 = 0

    if (k1>0) & (k2>0) :
        u1 = (k1-k2)
        if u1 >= 0 :
            q1 = u1
        else :
            q1 = -(u1)
        sum1 = q1*m1
        if (2*m1) > (m2):
            if k1 < k2 :
                sum2 = m2*(k1)
            else :
                sum2 = m2*(k2)
        else :
            if k1 < k2 :
                sum2 = (2*m1)*(k1)
            else :
                sum2 = (2*m1)*(k2)
    elif (k1<0) & (k2<0) :
        k1 = -(k1)
        k2 = -(k2)
        u1 = (k1-k2)
        if u1 >= 0 :
            q1 = u1
        else :
            q1 = -(u1)
        sum1 = q1*m1
        if (2*m1) > (m2):
            if k1 < k2 :
                sum2 = m2*(k1)
            else :
                sum2 = m2*(k2)
        else :
            if k1 < k2 :
                sum2 = (2*m1)*(k1)
            else :
                sum2 = (2*m1)*(k2)
    elif (k1==0) & (k2>0) :
        sum1 = 0
        sum2 = k2*m1
    elif (k2==0) & (k1>0) :
        sum1 = k1*m1
        sum2 = 0
    elif (k1==0) & (k2<0) :
        k2 = -(k2)
        sum1 = 0
        sum2 = k2*m1
    elif (k2==0) & (k1<0) :
        k1 = -(k1)
        sum1 = k1*m1
        sum2 = 0
    else :
        if k1 >= 0 :
            k1 = k1
        else :
            k1 = -(k1)
        if  k2 >= 0 :
            k2 = k2
        else :
            k2 = -(K2)
        sum1 = k1*m1
        sum2 = k2*m2



    def add(s1,s2) :
        totBestSum = s1 +s2
        return totBestSum


    bbb = add(sum1,sum2)
    print(bbb)

    t= t-1
