A. Разбиваем лагерь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Летом все участники олимпиадных кружков «Летово» собираются в поход. Руководители похода заранее решили рассчитать количество палаток, которое необходимо взять с собой. Все палатки, которые есть на складе, трёхместные (вмещают не более $$$3$$$ человек).

Всего среди участников кружков есть $$$a$$$ интровертов, $$$b$$$ экстравертов и $$$c$$$ универсалов.

  • Каждый интроверт хочет жить в палатке один. Таким образом, палатка с интровертом обязана содержать ровно одного человека — самого этого интроверта.
  • Каждый экстраверт хочет жить в палатке с ещё двумя людьми. Таким образом, палатка с экстравертом обязана содержать ровно трёх человек.
  • Каждого универсала устроит любой вариант: жить одному, вдвоём или втроём.

Скажите, какое минимальное количество палаток необходимо взять с собой, чтобы все участники смогли разместиться в соответствии со своими предпочтениями! Если же разместить участников так, чтобы выполнить все пожелания, невозможно, выведите $$$-1$$$.

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

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

Каждый набор описывается одной строкой, содержащей три целых числа $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) — количество интровертов, экстравертов и универсалов соответственно.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество палаток или $$$-1$$$, если разместить участников невозможно.

Пример
Входные данные
10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000
Выходные данные
3
-1
3
-1
3
28
0
7
8
1666666667
Примечание

В первом наборе входных данных $$$1$$$ палатку нужно будет отдать интровертам, ещё в $$$1$$$ палатке будут жить два экстраверта и один универсал, в последней будут жить два универсала. Итого $$$3$$$ палатки.

Во втором наборе три экстраверта возьмут $$$1$$$ палатку, также $$$1$$$ палатку возьмет интроверт. Тогда останется один экстраверт и один универсал. Этот экстраверт никак не сможет поселиться с кем-то втроем.