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

Монокарп играет в компьютерную игру. Он должен уничтожить $$$n$$$ монстров, у $$$i$$$-го из них $$$h_i$$$ здоровья.

У Монокарпа есть два заклинания, каждое из которых он может применить произвольное количество раз (возможно, ноль) и в произвольном порядке:

  • выбрать ровно двух живых монстров и уменьшить их здоровье на $$$1$$$;
  • выбрать ровно одного живого монстра и убить его.

Когда здоровье монстра становится равным $$$0$$$, он умирает.

Какое наименьшее количество раз Монокарп должен применить заклинания, чтобы убить всех монстров?

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество монстров.

Во второй строке записаны $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 100$$$) — здоровье каждого монстра.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.

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

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

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

В первом наборе входных данных изначальный список здоровья $$$[1, 2, 1, 2]$$$. Применяются три заклинания:

  • первое заклинание на монстров $$$1$$$ и $$$2$$$ — монстр $$$1$$$ умирает, у монстр $$$2$$$ здоровье становится $$$1$$$, новый список здоровья $$$[0, 1, 1, 2]$$$;
  • первое заклинание на монстров $$$3$$$ и $$$4$$$ — монстр $$$3$$$ умирает, у монстр $$$4$$$ здоровье становится $$$1$$$, новый список здоровья $$$[0, 1, 0, 1]$$$;
  • первое заклинание на монстров $$$2$$$ и $$$4$$$ — оба монстра $$$2$$$ и $$$4$$$ умирают.

Во втором наборе входных данных изначальный список здоровья $$$[2, 4, 2]$$$. Применяются три заклинания:

  • первое заклинание на монстров $$$1$$$ и $$$3$$$ — у обоих монстров здоровье становится $$$1$$$, новый список здоровья $$$[1, 4, 1]$$$;
  • второе заклинание на монстра $$$2$$$ — монстр $$$2$$$ умирает, новый список здоровья $$$[1, 0, 1]$$$;
  • первое заклинание на монстров $$$1$$$ и $$$3$$$ — оба монстра $$$1$$$ и $$$3$$$ умирают.

В третьем наборе изначальный список здоровья $$$[1, 2, 3, 4, 5]$$$. Применяются пять заклинаний. $$$i$$$-е из них убивает $$$i$$$-го монстра вторым заклинанием. Последовательность списков здоровья: $$$[1, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 0]$$$.