B. Lunchtime Fruits
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В школьной столовой есть четыре типа фруктов: абрикосы, бананы, яблоки и груши. В меню на сегодня три разных вида полдника:

  1. два абрикоса, один банан и одно яблоко;
  2. два абрикоса и два яблока;
  3. один абрикос, один банан, два яблока и одна груша.
Сотрудники хотят из имеющихся продуктов составить как можно больше полдников для детей. Помогите им это сделать!

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

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество сценариев, для которых нужно решить задачу.

Следующие $$$t$$$ строк содержат описание тестовых сценариев каждая. Каждая строка содержит четыре числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$1 \le a, b, c, d \le 10^9$$$) — количество абрикосов, бананов, яблок и груш соответственно.

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

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

Система оценки
ПодзадачаБаллыОграничения
$$$1$$$$$$10$$$$$$t \le 10$$$; $$$a, b, c, d \le 10$$$
$$$2$$$$$$20$$$$$$t \le 10^4$$$; $$$a, b, c, d \le 10$$$
$$$3$$$$$$20$$$$$$t \le 10$$$; $$$a, b, c, d \le 200$$$
$$$4$$$$$$20$$$$$$t \le 10$$$; $$$a, b, c, d \le 10^6$$$
$$$5$$$$$$30$$$Без дополнительных ограничений
Пример
Входные данные
6
3 3 3 3
3 1 4 1
4 3 2 1
3 3 6 5
9 7 6 7
9 10 10 6
Выходные данные
2
2
2
3
5
6
Примечание

В первом сценарии можно сделать два полдника: один типа $$$1$$$ и один типа $$$3$$$.

Во втором сценарии подойдет набор полдников $$$(2, 3)$$$.

В третьем сценарии оптимальный набор $$$(1, 1)$$$.

В четвертом сценарии можно сделать три полдника типа $$$3$$$.