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.
In the first test we can sort the participants into four cars like this:
the third group (consisting of four participants), the fourth group (consisting of three participants), the fifth group (consisting of three participants), the first and the second group (consisting of one and two participants, correspondingly). There are other ways to sort the groups into four cars.
