题目描述

Monocarp 正在玩一款电脑游戏。他需要击杀 $n$ 个怪物，第 $i$ 个怪物有 $h_i$ 点生命值。

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

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

当怪物的生命值变为 $0$ 时，该怪物死亡。

请问 Monocarp 至少需要施放多少次法术才能击杀所有怪物？

输入格式

第一行包含一个整数 $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 \times 10^4$。

输出格式

对于每个测试用例，输出一个整数，表示 Monocarp 至少需要施放多少次法术才能击杀所有怪物。

说明/提示

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

由 ChatGPT 4.1 翻译

样例

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

3
3
5