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.
# ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
# ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
# ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
# ░░░░░░█░█░░▀░░░░░░░░▀░░█░█░░░░░
# ░░░░░░█░█░░░▀░░░░░░▀░░░█░█░░░░░
# ░░░░░░█░█░░░░▀░░░░▀░░░░█░█░░░░░
# ░░░░░░█░█▄░░░░▀░░▀░░░░▄█░█░░░░░
# ░░░░░░█░█░░░░░░██░░░░░░█░█░░░░░
# ░░░░░░█░▀░░░░░░░░░░░░░░▀░█░░░░░
# ░░░░░░█░░░░░░  ░░░░░  ░░░█░░░░░
# ░░░░░░█░░░░░░ ░ ░░░ ░ ░░░█░░░░░
# ░░░░░░▀░░░░░░ ░░ ░ ░░ ░░░▀░░░░░
# ░░░░░░░░░░░░░ ░░░ ░░░ ░░░░░░░░░

MOD =  1000000007
mod = 10009
#import time
#import heapq
#import math
#import string
#import bisect
#import collections
 
def primeseive(n):
    prime = [True for i in range(n+1)]
    p=2
    while p*p<=n:
        if prime[p]==True:
            for i in range(p*p,n+1,p):
                prime[i]=False
        p+=1
    ans = [i for i in range(2,n+1) if prime[i]]
    print(ans)

def checkprime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True

def primeFactors(n): 
    prime = set()
    while n % 2 == 0: 
        prime.add(2)
        n = n//2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            prime.add(i)
            n = n//i 
    if n > 2: 
        prime.add(n)
    return list(prime)

def sort_dict(key_value):
    return sorted(key_value.items(), key = lambda kv:(kv[1], kv[0]))

def xymodm(x,y,m):
    res = 1
    x=x%m
    if x==0:
        return 0
    while y>0:
        if y&1:
            res =(res*x)%m
        y = y//2
        x = (x*x)%m
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

#------------------------------------------------
def solve(x,y,a,b):
    if a+a<=b:
        ans = (x+y)*a
    else:
        if x>=y:
            ans = abs(x-y)*a + y*b
        else:
            ans = abs(x-y)*a + x*b

    print(ans)

for i in range(int(input())):
    #x,y,l,r= map(int,input().split())
    n,k= map(int,input().split())
    a,b= map(int,input().split())
    #n = int(input())
    #a = list(map(int,input().split()))
    #b = list(map(int,input().split()))
    #l,r= map(int,input().split())
    #n = int(input())
    #s = input()
    #sa = list(map(str,input().split()))
    #b = list(map(int,input().split()))
    #st = time.process_time()
    solve(n,k,a,b)
    #print(s)
    #pt = solve(s)
    #print(pt)
    #print("yes" if pt==1 else "no")
    #print("Linear : ",time.process_time() - st)