Polycarp has x of red and y of blue candies. Using them, he wants to make gift sets. Each gift set contains either a red candies and b blue candies, or a blue candies and b red candies. Any candy can belong to at most one gift set.

Help Polycarp to find the largest number of gift sets he can create.

For example, if x = 10, y = 12, a = 5, and b = 2, then Polycarp can make three gift sets: 

  * In the first set there will be 5 red candies and 2 blue candies; 
  * In the second set there will be 5 blue candies and 2 red candies; 
  * In the third set will be 5 blue candies and 2 red candies. 



Note that in this example there is one red candy that Polycarp does not use in any gift set.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case consists of a single string containing four integers x, y, a, and b (1 ≤ x, y, a, b ≤ 10^9).

Output

For each test case, output one number — the maximum number of gift sets that Polycarp can make.

Example

Input


9
10 12 2 5
1 1 2 2
52 311 13 27
1000000000 1000000000 1 1
1000000000 1 1 1000000000
1 1000000000 1000000000 1
1 2 1 1
7 8 1 2
4 1 2 3


Output


3
0
4
1000000000
1
1
1
5
0
import java.util.*;
import java.io.*;
 
public class Main2 {
	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; }}
	static long mod = (long)(1e9+7);
//	static long mod = 998244353;
//	static Scanner sc = new Scanner(System.in);
	static FastReader sc = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);
	public static void main (String[] args) {
		int t = 1;
    	t = sc.nextInt();
	    z : for(int tc=1;tc<=t;tc++) {
	    	long x=sc.nextLong(),y = sc.nextLong(), a = sc.nextLong(), b = sc.nextLong();
	    	if(x>y) {
	    		long temp = x;
	    		x = y;
	    		y = temp;
	    	}
	    	if(a>b) {
	    		long temp = a;
	    		a = b;
	    		b = temp;
	    	}
	    	long l = 0, h = (long)(1e9+1);
	    	long ans = 0;
	    	while(l<=h) {
	    		long mid = (l+h)/2;
	    		boolean is = false;
	    		long lo = 0, hi = mid;
	    		while(lo<=hi) {
	    			long tm = (lo+hi)/2;
	    			long tma = mid - tm;
	    			if(y/b<tm) {
	    				hi = tm-1;
	    				continue;
	    			}
	    			if(x/b<tma) {
	    				lo = tm+1;
	    				continue;
	    			}
	    			long ty = y - tm*b;
	    			long tx = x - tma*b;
	    			if(ty/a<tma) {
	    				hi = tm-1;
	    				continue;
	    			}
	    			if(tx/a<tm) {
	    				lo = tm+1;
	    				continue;
	    			}
	    			is = true;
	    			break;
	    		}
	    		if(is) {
	    			ans = mid;
	    			l = mid+1;
	    		}
	    		else {
	    			h = mid-1;
	    		}
	    	}
	    	out.write(ans+"\n");
	    }
		out.close();
	}
	static long gcd(long a,long b) { if(b==0) return a; return gcd(b,a%b); }
	private static void sort(int[] a) {List<Integer> k = new ArrayList<>();for(int val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);}
	private static void ini(List<Integer>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}}
	private static void init(List<int[]>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}}
	private static void sort(long[] a) {List<Long> k = new ArrayList<>();for(long val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);}
}