В одной очень известной олимпиаде участвуют более ста человек. Олимпиада состоит из двух этапов: отборочного и заключительного. В заключительный этап проходят хотя бы сто участников. Отборочный же этап состоит из двух туров.
Результатом отборочного этапа является сумма баллов за два тура. Но, к сожалению, жюри потеряли финальную таблицу результатов, и у них остались только отдельные результаты по первому и второму туру.
В каждом туре участников упорядочивают по невозрастанию баллов. В случае, если два участника набрали одинаковый балл, они упорядочиваются по номеру паспорта. В соответствии с законодательством номера паспортов всех участников различны.
В первом туре участник на сотом месте набрал $$$a$$$ баллов. Дополнительно, жюри выяснили, что все участники первого тура, занявшие места от первого до сотого включительно, набрали не менее $$$b$$$ баллов во втором туре.
Во втором туре участник на сотом месте набрал $$$c$$$ баллов. Жюри также выяснили, что все участники второго тура, занявшие места от первого до сотого включительно, набрали не менее $$$d$$$ баллов в первом туре.
Упорядочим всех участников по невозрастанию суммы их баллов за два тура. При равенстве результатов упорядочим участников по номеру паспорта. Тогда проходной балл для попадания в заключительный этап — это сумма баллов за оба тура у участника на сотом месте.
По данным $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ помогите жюри узнать, каким может быть минимальный проходной балл на заключительный этап.
Вам нужно получить ответ для $$$t$$$ наборов входных данных.
В первой строке задано целое число $$$t$$$ ($$$1 \leq t \leq 3025$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.
В первой строке каждого набора входных данных задано четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \le a,\,b,\,c,\,d \le 9$$$; $$$d \leq a$$$; $$$b \leq c$$$).
Можно показать, что для любых входных данных, удовлетворяющих ограничениям из условия, существует хотя бы один корректный вариант проведения олимпиады.
Для каждого набора входных данных выведите одно целое число — минимальный возможный проходной балл на заключительный этап.
2 1 2 2 1 4 8 9 2
3 12
В первом наборе входных данных на олимпиаду могут отбираться $$$101$$$ человек с баллами $$$1$$$ и $$$2$$$ за первый и второй тур, соответственно. Сумма баллов у участника на 100-м место будет равна $$$3$$$.
Во втором наборе на олимпиаду могло происходить следующее:
