d-the-judgment-day

Today is the judgment day of Pokemons worldcup and all the audience are waiting outside the stadium. Many families has come to see the world cup (say N). Each family has atleast one and atmost four members and they want to seat together. The sitting arrangement in the stadium is such that one   row can hold maximum four peoples. what is the minimum numbers of  rows required such that all the family members sit together ( in one row there can be more than one family ) ? 
Input:
First line of input contains T - total no. of test cases
Each test case is followed by two lines: 
First list  is N denoting total no of families 
Second line contains N space separated  integers S1,S2 ..... SN denoting size of family 

Output:
Print the single number — the minimum number of rows required.
Constraints: 
      1 ≤T ≤ 100 
     3 ≤ N ≤ 100 
    1 ≤ S1,S2 ..... SN ≤ 4

SAMPLE INPUT
2
5
1 2 4 3 3
8
2 3 4 4 2 1 3 1

SAMPLE OUTPUT
4
5

Explanation

In the first test case we can sort the families into 4 rows like this:
the third family (consisting of four members),
the fourth family (consisting of three members),
the fifth family(consisting of three members),
the first and the second family(consisting of one and two members, correspondingly).

There are other ways to sort the families into four rows.

Source: hackerearth | Difficulty: EASY


Solutions: