indiahacks-and-ola-cabs

After the IndiaHacks Contest is over n groups of participants wants to go home. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to together. They decided to get there by Ola Cabs. Each cab can carry at most four passengers. What minimum number of cabs will the participants need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input
The first line contains integer t denoting the test cases. Followed by t lines having n (1 ≤ n ≤ 105) — the number of groups of participants. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of participants in the i-th group.

Output
Print t lines consisting the single number — the minimum number of ola cabs necessary to drive all participants.
Register for IndiaHacksSAMPLE INPUT
2
5
1 2 4 3 3
8
2 3 4 4 2 1 3 1

SAMPLE OUTPUT
4
5

Register for IndiaHacks

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: