题目描述

Monocarp正在玩电脑游戏，它杀了n个怪物，每一个怪物都有对应的健康度。

Monocarp的角色有两个咒语，他可以任意多次（可能是零）释放：

• 精确选择两个活着的怪物，并将其生命值降低1
• 选择一个怪物并杀死它。

当怪物的生命值为0时，它就会死亡。

为了杀死所有怪物，Monocarp应该执行的最低施法次数是多少？

输入

第一行包含一个整数t（1≤t≤10^4）—测试用例的数量。

每个测试用例的第一行包含一个整数n(1≤n≤100) —怪物的数量。

第二行包含n个整数，h1,h2,,,（1≤hi≤100） —每个怪物的健康。

输出

对于每个测试用例，打印一个整数——为了杀死所有怪物，Monocap应该执行的最小法术施放次数。

3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5

3
3
5

Note

In the first testcase, the initial health list is $[1, 2, 1, 2]$. Three spells are casted:

• the first spell on monsters $1$ and $2$ — monster $1$ dies, monster $2$ has now health $1$, new health list is $[0, 1, 1, 2]$;
• the first spell on monsters $3$ and $4$ — monster $3$ dies, monster $4$ has now health $1$, new health list is $[0, 1, 0, 1]$;
• the first spell on monsters $2$ and $4$ — both monsters $2$ and $4$ die.

In the second testcase, the initial health list is $[2, 4, 2]$. Three spells are casted:

• the first spell on monsters $1$ and $3$ — both monsters have health $1$ now, new health list is $[1, 4, 1]$;
• the second spell on monster $2$ — monster $2$ dies, new health list is $[1, 0, 1]$;
• the first spell on monsters $1$ and $3$ — both monsters $1$ and $3$ die.

In the third testcase, the initial health list is $[1, 2, 3, 4, 5]$. Five spells are casted. The $i$-th of them kills the $i$-th monster with the second spell. Health list sequence: $[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]$.