G. Подарочный набор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть $$$x$$$ красных и $$$y$$$ синих конфет. Из них он хочет составить подарочные наборы. Каждый подарочный набор будет содержать либо $$$a$$$ красных конфет и $$$b$$$ синих конфет, либо наоборот — $$$a$$$ синих конфет и $$$b$$$ красных конфет.

Помогите Поликарпу понять, какое наибольшее число подарочных наборов он может составить.

Например, если $$$x = 10$$$, $$$y = 12$$$, $$$a = 5$$$ и $$$b = 2$$$, то он может составить три подарочных набора:

  • В первом наборе будет $$$5$$$ красных конфет и $$$2$$$ синие;
  • Во втором наборе будет $$$5$$$ синих конфет и $$$2$$$ красные;
  • В третьем наборе будет $$$5$$$ синих конфет и $$$2$$$ красные.

У Поликарпа останется одна красная конфета, используя которую, он не сможет собрать еще один подарочный набор.

Входные данные

В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из одной строки в которой находятся четыре целых числа $$$x$$$, $$$y$$$, $$$a$$$ и $$$b$$$ ($$$1 \le x, y, a, b \le 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите одно число — максимальное количество подарочных наборов, которое может собрать Поликарп.

Пример
Входные данные
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
Выходные данные
3
0
4
1000000000
1
1
1
5
0