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

Ева — начинающий стендап комик. На ее первое выступление пришли целых два зрителя: Алиса и Боб.

Ева подготовила $$$a_1 + a_2 + a_3 + a_4$$$ шуток, сгруппированных по типам:

  • тип 1: Алисе и Бобу нравятся;
  • тип 2: Алисе нравятся, а Бобу нет;
  • тип 3: Бобу нравятся, а Алисе нет;
  • тип 4: ни Алисе, ни Бобу не нравятся.

Изначально настроение обоих зрителей $$$0$$$. Когда зритель слышит шутку, которая ему нравится, его настроение увеличивается на $$$1$$$. Когда зритель слышит шутку, которая ему не нравится, его настроение уменьшается на $$$1$$$. Если настроение становится отрицательным (строго меньше нуля), то зритель уходит.

Когда кто-то уходит, Еве становится грустно, и она заканчивает выступление. Если никто не уходит, а у Евы заканчиваются шутки, то она тоже заканчивает выступление.

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

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

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

В единственной строке каждого набора входных данных записаны четыре целых числа $$$a_1, a_2, a_3, a_4$$$ ($$$0 \le a_1, a_2, a_3, a_4 \le 10^8$$$; $$$a_1 + a_2 + a_3 + a_4 \ge 1$$$) — количество шуток каждого типа, которые подготовила Ева.

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

На каждый набор выходных данных выведите одно целое число — наибольшее количество шуток, которые Ева может рассказать до того как хотя бы один из зрителей уйдет или как у нее закончатся шутки.

Пример
Входные данные
4
5 0 0 0
0 0 0 5
2 5 10 6
3 0 0 7
Выходные данные
5
1
15
7
Примечание

В первом наборе входных данных Ева подготовила только шутки первого типа. Поэтому тут не выберешь порядок. Она рассказывает все свои штуки, и Алисе, и Бобу они нравятся. Их настроение становится $$$5$$$. Выступление заканчивается после того как у Евы заканчиваются шутки.

Во втором наборе входных данных Ева подготовила только шутки четвертого типа. Опять же не выберешь порядок. Она рассказывает шутку, и ни Алисе, ни Бобу она не нравится. Их настроение уменьшается на один, становится $$$-1$$$. У них обоих отрицательное настроение, поэтому они оба уходят, и выступление заканчивается.

В третьем наборе входных данных Ева сначала рассказывает обе шутки первого типа. У Алисы и Боба становится настроение $$$2$$$. Затем $$$2$$$ шутки третьего типа. Настроение Алисы $$$0$$$. Настроение Боба $$$4$$$. Затем $$$4$$$ шутки второго типа. Настроение Алисы $$$4$$$. Настроение Боба $$$0$$$. Затем еще $$$4$$$ шутки третьего типа. Настроение Алисы $$$0$$$. Настроение Боба $$$4$$$. Затем оставшуюся шутку второго типа. Настроение Алисы $$$1$$$. Настроение Боба $$$3$$$. Затем еще шутку третьего типа и четвертого типа, например. Настроение Алисы становится $$$-1$$$, и она уходит.

В четвертом наборе входных данных Ева должна сначала рассказать шутки, которые нравятся обоим зрителям, затем шутки, которые не нравятся никому. Она может рассказать $$$4$$$ шутки четвертого типа, пока зрители не уйдут.