← 返回题目列表

Codeforces · 1538/G

G. 礼品套装

中文机器翻译题面 查看原题

Polycarp 有 $$$x$$$ 红色糖果和 $$$y$$$ 蓝色糖果。他想用它们制作礼品套装。每个礼品套装包含 $$$a$$$ 红色糖果和 $$$b$$$ 蓝色糖果,或 $$$a$$$ 蓝色糖果和 $$$b$$$ 红色糖果。任何糖果最多可以属于一套礼品套装。

帮助坡旅甲找到他可以制作的最多数量的礼品套装。

例如,如果 $$$x = 10$$$、$$$y = 12$$$、$$$a = 5$$$ 和 $$$b = 2$$$,则 Polycarp 可以制作三套礼品套装:

- 第一组会有 $$$5$$$ 红色糖果和 $$$2$$$ 蓝色糖果;
- 第二组将有 $$$5$$$ 蓝色糖果和 $$$2$$$ 红色糖果;
- 第三组将有 $$$5$$$ 蓝色糖果和 $$$2$$$ 红色糖果。

请注意,在此示例中,Polycarp 没有在任何礼品套装中使用一颗红色糖果。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例由一个字符串组成,其中包含四个整数 $$$x$$$、$$$y$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le x, y, a, b \le 10^9$$$)。

输出

对于每个测试用例,输出一个数字——Polycarp 可以制作的礼品套装的最大数量。

示例

输入 #1

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

输出 #1

3
0
4
1000000000
1
1
1
5
0