题目描述

LLL 在 NOIP 前想愉悦身心，于是设计了一个有趣的纸牌游戏。

该游戏中有 $n$ 种不同的牌，编号为 $1,2,\dots,n$，第 $i$ 种牌有 $v_i$ 张。

总共有四种出牌方法：

• 单牌：出一张单牌。
• 对子：出两张同种的牌。
• 炸：出四张同种的牌。
• 三带一：出三张同种的牌和一张不同种的牌。

当出完所有牌后即可获得游戏胜利。

LLL 想知道最少需要出多少次牌才能获得游戏胜利，请你帮他求出这个值。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示数据组数。接下来，对于每组数据：

• 第一行，一个正整数 $n$，表示牌的种类数。
• 第二行，$n$ 个非负整数 $v_1, \ldots, v_n$，表示第 $i$ 种牌的数量。

输出格式

对于每组测试数据：

• 仅一行，一个整数，表示最少需要出多少次牌才能获得游戏胜利。

样例

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

2
4
6

样例 1 解释

对于第一组数据，可以先出 $1, 1, 1, 2$（三带一），再出 $1, 1$（对子）。

对于第二组数据，可以用 $4$ 次出完：

• 出 $1, 1, 1, 1$（炸）。
• 出 $2, 2, 2, 2$（炸）。
• 出 $3, 3, 3, 4$（三带一）。
• 出 $4, 4$（对子）。

样例 2

见附件中的 card/card2.in 与 card/card2.ans。

该组样例满足测试点 $2\sim 3$ 的约束条件。

样例 3

见附件中的 card/card3.in 与 card/card3.ans。

该组样例满足测试点 $5\sim 6$ 的约束条件。

样例 4

见附件中的 card/card4.in 与 card/card4.ans。

该组样例满足测试点 $9\sim 10$ 的约束条件。

数据范围

对于所有测试数据，保证：$1\le T\le 10$，$1\le n\le3\times10^5$，$0\le v_i\le10^9$。

测试点编号	$n\le$	$v_i\le$
$1$	$2$	$10^9$
$2\sim 3$	$5$	$5$
$4$		$10^9$
$5\sim 6$	$50$
$7$	$3\times 10^5$	$2$
$8$		$3$
$9\sim 10$		$10^9$

下发文件

通过点击此链接下载下发文件。