1280 : 出租车

时间限制:1 Sec 内存限制:128 MiB
提交:67 答案正确:26

提交 状态 讨论区

题目描述

放学了,有 n 组ZZULI的学生准备坐出租车到科学大道公交站牌,现已知第i组有si(1 <= si <= 4)名学生,每一辆出租车最多只能坐4个人,如果同一组的学生必须坐同一辆车(但是一辆车可以坐很多组的学生),最少需要多少辆出租车呢。

输入

首先输入一个整数N,表示有N组测试实例。
每组实例的第一行输入一个整数n(1 <= n <= 105),第二行输入n个整数s1,s2,...,sn,表示每组学生的数量

输出

每组实例输出一个整数,表示最少需要多少辆出租车。

样例输入

复制
2
5
1 2 4 3 3
8
2 3 4 4 2 1 3 1

样例输出

复制
4
5

提示


			

来源

2012新生赛