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

Алиса и Боб собрались вечером, чтобы поиграть в увлекательную игру на последовательности из $$$n$$$ натуральных чисел, не превосходящих $$$4$$$. Правила игры слишком сложны для их описания, поэтому просто опишем критерий победы — Алиса побеждает, если исключающее ИЛИ всех чисел последовательности отлично от нуля, в противном случае же побеждает Боб.

Ребята позвали Еву, чтобы она выступала в качестве судьи. Изначально Алиса и Боб играют с $$$n$$$ числами. После одной игры Ева удаляет одно из чисел из последовательности, затем Алиса и Боб играют с $$$n-1$$$ числами, Ева снова удаляет одно из чисел, после чего Алиса и Боб играют с $$$n - 2$$$ числами. Так продолжается до тех пор, пока последовательность чисел не пуста.

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

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

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

Первая и единственная строка каждого набора содержит четыре целых числа $$$p_i$$$ ($$$0 \le p_i \le 200$$$) — количество единиц, двоек, троек и четвёрок в последовательности в начале игры.

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

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

Пример
Входные данные
5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9
Выходные данные
1
1
3
3
12
Примечание

В первом примере Боб выигрывает, когда Ева ещё не убрала ни одного числа.

Во втором примере Боб выигрывает, если Ева уберёт одну единицу и одну тройку.