题目描述

咕噜正在玩电脑游戏。他打算杀死 n 个怪兽，第 i 个怪兽的血量为h_i。

咕噜的角色拥有两种魔法咒语（可以任意次、任意顺序使用）：

1. 选择两个怪兽，各扣 1 滴血（即总共减少 2 点血）。
2. 选择一个怪兽，直接将其杀死（不管血量是多少）。

当怪兽的血量为 0 时，怪兽就死亡。

目标：

用 最少的操作次数 杀死所有怪兽。

输入格式

• 第 1 行：一个整数 t（1 ≤ t ≤ 10^4）表示数据组数
  接下来的 t 组，每组包括：
• 第 1 行：一个整数 n（1 ≤ n ≤ 100），表示怪兽数量
• 第 2 行：n 个整数 h₁, h₂, ..., h_n（1 ≤ h_i ≤ 100），表示每个怪兽的血量

保证：所有组中 ∑n ≤ 2×10^4

输出格式

共 t 行，每行一个整数，表示每组数据中杀死所有怪兽的最少操作次数。

输入样例 #1

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

输出样例 #1

3  
3  
5