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.


import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;










public class Main {
    public static int MAX_SIZE = 1000001 ;
    public static Vector<Boolean> isprime = new Vector<Boolean>(MAX_SIZE);
    public static Vector<Integer> primes = new Vector<Integer>(MAX_SIZE) ;
    public static Vector<Integer> SPF = new Vector<Integer>(MAX_SIZE);



    public static void sieve (int n ) {
        isprime.set(0,false);
        isprime.set(1, false) ;
        for (int i  = 2 ; i < n ;  i ++ )  {
            if (isprime.get(i)) {
                primes.add(i);
                SPF.add(i);
            }
            for (int j = 2 ; i*primes.get(j) <= n  ; j +=i ) {

            }

        }

    }


    public static ArrayList<Stack<Integer>> as = new ArrayList<Stack<Integer>>();


    public static int k ;
    public static Stack<Integer>q=new Stack<Integer>();

    public static void  permutation (int [] a,int n , int mask, int taken) {

        if (taken == n  ) {

            arr = q.toArray();
            backtrack((int)arr[0],0, 1);
            return ;


        }
        else {
            for(int i = 0 ; i < n ; i++  ) {
                if ((mask &(1 << i)) == 0 ) {
                    q.add((int)a[i]);


                    permutation(a,n, mask | (1 <<i) , taken+1);
                    q.pop();
                }
            }
        }

    }








    public static boolean gsd(long x , int y) {
        for(int i = 2 ; i <= Math.min(y, x) ; i ++ ) {
            if (x%i == 0 && y%i == 0 ) return true;
        }
        return false;
    }
    public static int s(long x) {
        int sum = 0 ;
        do {
            sum += x%10 ;
            x /= 10;
        }while(x >0 );
        return sum;
    }
    public static int right(String s) {
        int c = 0 ;
        for(int i = s.length()-1 ; i>=0; i -- ) {
            if(s.charAt(i) == 'a') c++ ;
            else break;
        }
        return c;
    }
    public static int left(String s) {
        int c = 0 ;
        for(int i = 0 ; i<s.length(); i ++ ) {
            if(s.charAt(i) == 'a') c++ ;
            else break;
        }
        return c;
    }
    public static boolean onlyas (String s) {
        for (int i = 0 ; i < s.length() ; i ++ ) {
            if (s.charAt(i) != 'a') return false ;
        }return true;
    }
    public static String convert(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < s.length() ; i ++ ) {
            if (s.charAt(i) == '1') sb.append("0");
            else sb.append("1");
        }
        return sb.toString();
    }
    public static int check (String s) {
//		boolean flag = false ; 
        for (int i = 0 ; i < s.length() ; i ++) {
            if (Character.isDigit(s.charAt(i)) ) {
                for (int j = i ; j <s.length() ; j ++ ) {
                    if (!Character.isDigit(s.charAt(j)))return 0 ;
                }
                return 1 ;
            }

        }
        return 1;
    }
    public static String s26 (int n) {
        StringBuilder st = new StringBuilder();
        while (n >0) {
            int x = n%26 ;
            n /= 26 ;
            if (x-1 <0 ) {
                x = 26;n-- ;
            }
            st.insert(0, letters[x-1]);
        }
        return st.toString();
    }

    public static int sum = 0 ;
    public static int tokens = 0 ;
    public static Object arr [] = new Integer [5];
    public static boolean flag = false ;
    public static void backtrack (int ss , int idx , int tks) {

        if (tks == 5 )  {
//			System.out.println(ss + " ");
            if (ss  == 23 ) {//System.out.print(ss+" " );
                flag = true ; return ;
            }
        }else {
            backtrack(ss+ (int)arr[idx+1], idx+1, tks+1);
            backtrack(ss*(int)arr[idx+1], idx+1, tks+1);
            backtrack(ss-(int)arr[idx+1], idx+1, tks+1);

        }

    }
    public static int length (int n) {
        int l = 0 ;
        while (n > 0 ) {
            l ++ ;
            n /=10 ;
        }
        return l ;
    }
    public static int GCD (int x , int y  )  {
        if (x == y ) return x ;

        if (x > y ) return GCD(x-y , y ) ;
        else return GCD(x , y -x);
    }

    public static int low (int k ) {
        return (k)*(k+1)/2 ;
    }
    public static int high (int n , int k) {
        return (k)*(2*n-k+1)/2 ;
    }
    public static char [] letters = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'
            ,'P','Q','R','S','T','U','V','W','X','Y', 'Z'};
    public static void main(String[] args)  throws IOException, InterruptedException{
        PrintWriter pw = new PrintWriter(System.out);
        Scanner sc = new Scanner (System.in);

        int t  = sc.nextInt();
        while (t -- > 0 ) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c1 = (x+y) * a ;
            long c2 = (Long.min(x,y)*b) ;c2+= (Math.abs(x-y)*a);
//            pw.println(c2);
            if (c1 < 0 ) pw.println(c2);
            else pw.println(Math.min(c1,c2));
        }
        pw.close ();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(String file) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

    }


}
 
/*
while (true) {
		
		
		int []a = new int [5];
	
		for (int i = 0 ; i < 5 ; i ++ ) {
			arr[i]= sc.nextInt(); 
			a[i]= (int)arr[i];; 
		}
		if (a[0] == 0) break ;
		permutation(a, 5, 0, 0);
	
		pw.println(flag ? "Possible":"Impossible");
		}
 
			
*/