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
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.
