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.util.*;
import java.io.*;
 public class Main {
    public static void main ( String args[] ){
      FastReader sc = new FastReader();
      PrintWriter out = new PrintWriter (System.out); 
      int t = sc.nextInt(); 
      while(t-->0) {
	  long x = sc.nextLong(); 
    	  long y = sc.nextLong(); 
    	  long a = sc.nextLong(); 
    	  long b = sc.nextLong(); 
    	  long dif=Math.abs(x-y);
    	  long sum1 = 0 ; 
			sum1+=(1l*dif*a);
			long min=Math.min(x, y);
			sum1+=Math.min((1l*min*b),1l*min*a*2);
			System.out.println(sum1);
    	  

    
 }
    }
    
    
    
      
    
 
      
 
 
 
      
 
    
    static int [] freq (int [] a ) {
    	int max = 0 ; 
    	for (int i =0 ; i < a.length ; i++) {
    		max = Math.max(a[i], max); 
    		
    	}
    	int [] b = new int [max+1]; 
    	for (int i = 0 ; i < a.length ; i++) {
    		b[a[i]]++;
    		
    	}
    	return b ; 
    	
    }
     static class Graph 
    { 
        private int V;   // No. of vertices 
      
        // Array  of lists for Adjacency List Representation 
        private LinkedList<Integer> adj[]; 
      
        // Constructor 
        Graph(int v) 
        { 
            V = v; 
            adj = new LinkedList[v]; 
            for (int i=0; i<v; ++i) 
                adj[i] = new LinkedList(); 
        } 
      
        //Function to add an edge into the graph 
        void addEdge(int v, int w) 
        { 
            adj[v].add(w);  // Add w to v's list. 
        } 
      
        // A function used by DFS 
        void DFSUtil(int v,boolean visited[]) 
        { 
            // Mark the current node as visited and print it 
            visited[v] = true; 
            System.out.print(v+" "); 
      
            // Recur for all the vertices adjacent to this vertex 
            Iterator<Integer> i = adj[v].listIterator(); 
            while (i.hasNext()) 
            { 
                int n = i.next(); 
                if (!visited[n]) 
                    DFSUtil(n, visited); 
            } 
        } 
      
        // The function to do DFS traversal. It uses recursive DFSUtil() 
        void DFS(int v) 
        { 
            // Mark all the vertices as not visited(set as 
            // false by default in java) 
            boolean visited[] = new boolean[V]; 
      
            // Call the recursive helper function to print DFS traversal 
            DFSUtil(v, visited); 
        } 
    }
    public static long sum (long mid, long k ) {
    	long sum1 = (mid-1)*(mid) /2 ;
    	long sum2 = (k)*(k+1) /2 ; 
    	return sum2-sum1 ; 
    	
    	
    }
    public static void swap(Long []a ,int i , int j ) {
    	long temp = a[i]; 
    	a[i]= a[j]; 
    	a[j]= temp ; 
    	
    }
    
    static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 
		
		public FastReader() 
		{ 
			br = new BufferedReader(new
					InputStreamReader(System.in)); 
		} 
		
		String next() 
		{ 
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException  e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken(); 
		} 
		
		int nextInt() 
		{ 
			return Integer.parseInt(next()); 
		} 
		
		long nextLong() 
		{ 
			return Long.parseLong(next()); 
		} 
		
		double nextDouble() 
		{ 
			return Double.parseDouble(next()); 
		} 
		
		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		}
}
 }
  class Pair {
	int x ; 
	int y ; 
	public Pair(int x ,int y){
		this.x = x;
		this.y=y;}
}
 
  class Pair1 implements Comparable{
	int x ; 
	int y ; 
	public Pair1(int x ,int y){
		this.x = x;
		this.y=y;}
	public int compareTo(Object o) {
		Pair1 a = (Pair1) o ; 
		
		return (a.x-this.x);
	}
		
	}
 class Pair2 implements Comparable{
	int x ; 
	int y ; 
	public Pair2(int x ,int y){
		this.x = x;
		this.y=y;}
	public int compareTo(Object o) {
		Pair2 a = (Pair2) o ; 
		
		return (this.y-a.y);
	}
 }
 