CF1792A.GamingForces

Monocarp is playing a computer game. He's going to kill $n$ monsters, the $i$-th of them has $h_i$ health.

Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:

• choose exactly two alive monsters and decrease their health by $1$;
• choose a single monster and kill it.

When a monster's health becomes $0$, it dies.

What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?

Monocarp 正在玩一款电脑游戏。他需要杀死 $n$ 只怪物，其中第 $i$ 只怪物的生命值为 $h_i$。

Monocarp 的角色拥有两种法术，他可以以任意顺序、任意次数（包括零次）施放这两种法术：

• 选择恰好两只仍然存活的怪物，并将它们的生命值各减少 $1$；
• 选择一只怪物并直接将其杀死。

当一只怪物的生命值变为 $0$ 时，它即死亡。

Monocarp 至少需要施放多少次法术，才能杀死所有怪物？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 100$) — the number of monsters.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 100$) — the health of each monster.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^4$.

第一行包含一个整数 $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$。

For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.

对于每个测试用例，输出一个整数——Monocarp 为消灭所有怪物所需的最少施法次数。

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]$.

在第一个测试用例中，初始生命值列表为 $[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]$。