三连击杀

题目描述

有$n$个怪物，第$i$只怪物的血量为$blood_i$。

你现在有技能「三连击杀」，每使用一次这个技能，你都可以选择至少一个、至多三个不同的怪物，并任意决定这几个怪物的击杀顺序，产生如下伤害：

• 使第一个怪物的血量减少$9$；
• 如果选了第二个怪物，则使第二个怪物的血量减少$3$；
• 如果选了第三个怪物，则使第三个怪物的血量减少$1$。

当怪物的血量减少到小于或等于$0$时，则该怪物死亡。

你现在需要求出，最少使用多少次技能，能使所有怪物死亡。

输入格式

本题的每个测试点包含多组测试数据。

第一行，一个整数$R$，表示有$R$组测试数据。

每组测试数据格式如下：

第一行，一个整数$n$。

第二行，有$n$个正整数，第$i$个数表示$blood_i$。

输出格式

共输出$R$行，对每组数据输出一行一个整数表示答案。

数据范围与提示

• 对于$25\%$的数据，$n \leq 3$；
• 另有$5\%$的数据，每组询问满足$blood_i = 1$或$n \leq 3$；
• 对于所有数据，$1 \leq n \leq 20$，$1 \leq blood_i \leq 60$，$1 \leq R \leq 5$。

样例

5
20
60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60
20
18 42 44 33 23 7 42 44 8 23 26 48 11 58 43 15 4 29 24 52
3
9 2 2
3
45 17 3
3
3 5 18

93
46
2
6
3

5
2
8 14
3
43 59 17
2
9 7
10
12 23 34 45 56 60 54 43 32 21
20
53 36 35 29 56 11 35 19 38 35 18 49 50 12 53 38 19 59 38 60

3
10
2
30
58