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 \cdot 10^4$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 为了杀死所有怪物而应执行的最少施法次数。
示例
输入 #1
3 4 1 2 1 2 3 2 4 2 5 1 2 3 4 5
输出 #1
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]$$$。