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 Solution{
	long rem = 1000000000L;
	InputReader sc;
	boolean singleTest = false;
	
	public void solve(int test){
		int x = nextInt();
		int y = nextInt();
		int a = nextInt();
		int b = nextInt();
		
		long bDol = ((Math.min(x, y)*1L)*b);
		long max = ((long)Math.max(x, y));
		max -= ((long)Math.min(x, y));
		max *= a;
		
		long res = max+bDol;
		
		if((2*a) < (b)){
			res = ((a*1L)*(x+y));
		}
		
		println(res);
	}
	
	
	
	
	
	
	
	
	
	
	
	public int[] initialize(int[] arr, int len, int val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public long[] initialize(long[] arr, int len, long val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public boolean[] initialize(boolean[] arr, int len, boolean val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public int[] initialize(int[] arr, int val){
		return initialize(arr, arr.length, val);
	}
	public long[] initialize(long[] arr, long val){
		return initialize(arr, arr.length, val);
	}
	public boolean[] initialize(boolean[] arr, boolean val){
		return initialize(arr, arr.length, val);
	}
	
	public int nextInt(){
		return sc.nextInt();
	}
	public long nextLong(){
		return sc.nextLong();
	}
	public String next(){
		return sc.next();
	}
	public String nextLine(){
		return sc.nextLine();
	}
	public int[] nextArrInt(int n){
		int[] arr = new int[n];
		for(int i=0; i<n; i++){
			arr[i] = nextInt();
		}
		return arr;
	}
	public long[] nextArrLong(int n){
		long[] arr = new long[n];
		for(int i=0; i<n; i++){
			arr[i] = nextLong();
		}
		return arr;
	}
	public String[] nextArrWord(int n){
		String[] arr = new String[n];
		for(int i=0; i<n; i++){
			arr[i] = next();
		}
		return arr;
	}
	
	public void println(String str){
		System.out.println(str);
	}
	public void println(int num){
		System.out.println(num);
	}
	public void println(long num){
		System.out.println(num);
	}
	public void print(String str){
		System.out.print(str);
	}
	public void print(int num){
		System.out.print(num);
	}
	public void print(long num){
		System.out.print(num);
	}
	public void printArr(int[] arr){
		int n = arr.length;
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(int[] arr, int n){
		print(n+" ");
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(long[] arr){
		int n = arr.length;
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(long[] arr, int n){
		print(n+" ");
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	
	public Solution(){
		sc = new InputReader();
		
		int tests = 1;
		if(!singleTest){
			tests = sc.nextInt();
		}
        
        for(int t=1; t<=tests; t++){
			solve(t);
        }
	}
	
	public static void main(String[] args){
		new Solution();
	}
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;
	
	public InputReader(){
		InputStream stream = System.in;
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
	
    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
 
    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()) {
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch(IOException e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt(){
        return Integer.parseInt(next());
    }
	
	public long nextLong(){
		return Long.parseLong(next());
	}
	
	public String nextLine(){
		try{
			return reader.readLine();
		}catch(IOException e){
			throw new RuntimeException(e);
		}
	}
}