apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

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

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

## Examples
```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
```

Now solve the problem and return the code.