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.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class test {

 ////	public static void main(String[] args) {
////		Scanner sc = new Scanner(System.in);
////		int n=sc.nextInt();
////		int end=n%10;
////		int start=n/10;
////		if(end<=5) {
////			System.out.println(start*10);
////		}
////		else {
////			System.out.println((start+1)*10);
////		}
////	}
//	
	 public static String swapString(String a, int i, int j) {  
	        char[] b =a.toCharArray();  
	        char ch;  
	        ch = b[i];  
	        b[i] = b[j];  
	        b[j] = ch;  
	        return String.valueOf(b);  
	    } 
	static void generatepermutations(String str,int start,int end) {
		if(start==end-1) {
				System.out.println(str);
		}
		else {
			for(int i=start;i<end;i++) {
				str=swapString(str, start, i);
				
				generatepermutations(str, start+1, end);
				
				//str= swapString(str, start, i);
			}
		}
	}
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);		
//		int cases = sc.nextInt();
//		while(cases>0) {
//			int n=sc.nextInt();
//			sc.nextLine();
//			String r=sc.nextLine();
//			String b=sc.nextLine();
//			System.out.println("All permutations:");
//			generatepermutations(r,0,r.length());
//			
//			
//			
//			
//			
//			
//			
//			cases--;
//		}
//		
//	}
	static boolean checkHello(String input ,String answer) {
		//System.out.println(answer);
		if(answer.contains("hello")) {
			return true;
		}
		if(input.length()==0) {
			return false;
		}
	 return checkHello(input.substring(1),answer+input.charAt(0))||
					checkHello(input.substring(1),answer);
	}
	
	static boolean checkHelloNormal(String input) {
		String refer="hello";
		int j=0;
		for(int i=0;i<input.length();i++){
			if(j==5) {
				break;
			}
			if(input.charAt(i)==refer.charAt(j)) {
				j++;
			}
		}
		return j==5;
	}
	static String StringTask(String str) {
		str=str.toLowerCase();
		String newString="";
		for(int i=0;i<str.length();i++) {
			if(str.charAt(i)=='a'||str.charAt(i)=='e'||str.charAt(i)=='i'
			||str.charAt(i)=='o'||str.charAt(i)=='u'||str.charAt(i)=='y') {
			}
			else {
				newString+="."+str.charAt(i);
			}
		}
		return newString;
	}
	
	static String InterviewwithOleg(String str,int n) {
		boolean found=false;
		String newString="";
		for(int i=0;i<n;i++) {
			found=false;
			if(str.charAt(i)!='o') {
				newString+=str.charAt(i);
				continue;
			}
			for(int j=i+1;j<n-1;j+=2) {
		//		System.out.println(str.substring(j, j+2));
				if(str.substring(j, j+2).equals("go")) {
					found=true;
					i=j+1;
				}
				else {
					break;
				}
			}
			if(found) {
				newString+="***";
			}
			else {
				newString+="o";
			}
		}
		
		return newString;
		
		
		
	}
	
	static String MammothsGenomeDecoding(String str,int n) {
		String newString="";
		int A=0;
		int G=0;
		int C=0;
		int T=0;
		int question=0;
		for(int i=0;i<n;i++) {
			if(str.charAt(i)=='A') {
				A++;
			}
			else if(str.charAt(i)=='G') {
				G++;
			}
			else if(str.charAt(i)=='C') {
				C++;
			}
			else if(str.charAt(i)=='T') {
				T++;
			}
			else if(str.charAt(i)=='?') {
				question++;
			}
		}
		int max=Math.max(A, Math.max(G, Math.max(C,T)));
		int diff=(4*max)-A-G-C-T;
		 A=max-A;
		 G=max-G;
		 C=max-C;
		 T=max-T;
		if(question<diff||(question-diff)%4!=0) {
			return "===";
		}
		int extra=(question-diff)/4;
		A+=extra;G+=extra;C+=extra;T+=extra;
		for(int i=0;i<n;i++) {
			if(str.charAt(i)!='?') {
				newString+=str.charAt(i);
			}
			else {
				if(A==0 && G==0 && C==0 && T==0) {
					
					return "===";
				}
				if(A!=0) {
					newString+='A';
					A--;
				}
				else if(G!=0) {
					newString+='G';
					G--;
				}
				else if(C!=0) {
					newString+='C';
					C--;
				}
				else if(T!=0) {
					newString+='T';
					T--;
				}
			}
		}
		return newString;
	}
	
	static String removeLeadingZeros(String a) {
		int n=0;
		while(n!=a.length()) {
			if(a.charAt(n)!='0') {
				break;
			}
			n++;
		}
		return a.substring(n);
		
		
	}
	static char compareLongIntegers(String a,String b) {
		if(a.equals(b)) {
			return '=';
		}
		else {
			a=removeLeadingZeros(a);
			b=removeLeadingZeros(b);
			if(a.equals(b)) {
				return '=';
			}
			if(a.length()>b.length()) {
				return '>';
			}
			else if(a.length()<b.length()) {
				return '<';
			}
			else {
				int n=0;
				while(n!=a.length()) {
					if(a.charAt(n)>b.charAt(n)) {
						return '>';
					}
					else if(a.charAt(n)<b.charAt(n)) {
						return '<';
					}
					n++;
				}
				
			}
			return '=';
		}
	}
	
	
	static String hacking(String password,Map<String,Integer> store) {
		String answer="";
		for(int i=0;i<80;i+=10) {
			answer+=store.get(password.substring(i,i+10));
		}
		return answer;
	}
	
	static int faceDetection(char[][] arr,int r,int c) {
		int count=0;
		for(int i=0;i<r-1;i++) {
			for(int j=0;j<c-1;j++) {
				String temp="";
				temp+=(arr[i][j]+""+arr[i+1][j]+arr[i][j+1]+arr[i+1][j+1])+"";
				if(temp.contains("f") && temp.contains("a") && temp.contains("c")&& temp.contains("e")) {
					count++;
				}
			}
		}
		return count;
		
	}
	
	static String ValuedKeys(String a,String b) {
		for(int i=0;i<a.length();i++) {
			if(a.charAt(i)<b.charAt(i)) {
				return "-1";
			}
		}
		return b;
	}
	
	static int Antipalindrome(String s) {
		int i=0;
		int mid=(s.length()%2==0)?s.length()/2:s.length()/2+1;
		for(i=0;i<=mid;i++) {
			if(s.charAt(i)==s.charAt(s.length()-1-i)) {
				continue;
			}
			else {
				break;
			}
		}
		if(i==s.length()/2) {
			return 0;
		}
		else {
			return s.length();
		}
	}
	
	static int MoveBrackets(String s) {
	int count=0;
	int index=0;
	for(int i=0;i<s.length();i++) {
		if(s.charAt(i)=='(') {
			index++;
		}
		else {
			index--;
		}
		if(index<0) {
			count=Math.max(count, Math.abs(index));	
	}
	}
	return count;
	}
	
	
	static long RoadToZero(long x,long y,long a,long b) {
		
		long diff=Math.abs(x-y);
		return(Math.min((diff*a+(Math.min(x, y)*b)),(x+y)*a));
		
	}
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		int cases=sc.nextInt();
		while(cases>0) {
			long x=sc.nextLong();
			long y=sc.nextLong();
			long a=sc.nextLong();
			long b=sc.nextLong();
			System.out.println(RoadToZero(x, y, a, b));
			cases--;
		}

		

	}
}
