Problem: The manager of the Japanese sweets shop Tomogurido in Aizuwakamatsu City is a very skillful craftsman, but he feels a little mood. The buns made by the manager are very delicious, but the size varies depending on the mood at that time.

The store manager's wife, who couldn't see it, came up with the idea of ​​packing buns of different sizes and weights in a bag for sale. If you pack the buns in a bag so that they have a certain weight, you can sell them at a fixed price even if they are different in size, and there is also a surprise that you do not know what kind of buns are in until you open it. It may be for sale. When it was put on the market under the name of "Dismembered Manju", a new idea became a hot topic and Tomokuri-do quickly became popular. However, there was a problem, and the number of "separate buns" that could be made changed depending on how the buns were put in the bag, which sometimes caused waste. When you came to Tomokuri-do as a part-time job, you decided to create a program to pack it in a bag without waste.

There are 9 types of buns weighing 1 to 9. When packing in a bag, pack so that the total weight of the buns is exactly 10. The combination of buns is 1 + 1 + 2 + 4 + 2 = 10 or 1 + 1 + 1 + 1 + 1 + 5 = 10, and you can use any number of buns of the same weight.

Enter the information on the number of buns to be made and the weight of the buns, and create a program that outputs the maximum number of "separate buns" that can be made.



input

Given multiple datasets. The end of the input is indicated by a single zero. Each dataset is given in the following format:


n
m1 m2 ... mn


The number of buns n (2 ≤ n ≤ 100) is given on the first line. The second line gives the weight mi (1 ≤ mi ≤ 9) for each bun.

The number of datasets does not exceed 100.

output

For each dataset, the maximum number of "disjoint buns" that could be packed is output on one line.

Example

Input

5
4 9 1 3 8
10
8 5 3 6 2 1 4 5 4 5
9
5 7 3 8 2 9 6 4 1
0


Output

1
4
4

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

set<vector<int> > sv;
// vv[k] := 3個以上の合計が10になる饅頭の組合せ
vector<vector<int> > vv;
// v_sum[k] := vv[k]の合計
int v_sum[40] = {0};
// memo[k] := k 番目の組合せで饅頭が作れない
bool memo[40];

// v := 饅頭の集合, sum := v[0] + v[1] + ... + v[v.size()-1] (合計)
void f(vector<int> v, int sum = 0){
	if( sum == 10 ){
		if( 3 <= v.size() ){ 
			sort(v.begin(), v.end());
			sv.insert(v);
		}
	}else if( sum < 10 ){
		for(int i = 9; i >= 1 ; i-- ){
			v.push_back(i);
			f(v, sum + i);
			v.pop_back();
		}
	}
}

// 3個以上で10になる饅頭の組合せを事前に列挙しておく
void init(){
	vector<int> v;
	f(v);
	for(set<vector<int> >::iterator it = sv.begin() ; it != sv.end() ; ++it ){
		vv.push_back(*it);
	}
	for(int i = 0 ; i < vv.size() ; i++ ){
		int sum = 0;
		for(int j = 0 ; j < vv[i].size() ; j++ ){
			sum += vv[i][j];
		}
		v_sum[i] = sum;
	}
}

// v[k](k番目の合計が10になる組合せ)が使えるかどうかを返す
bool check(int k, vector<int> s){
	for(int i = 0 ; i < vv[k].size() ; i++ ){
		int e = vv[k][i];
		if( s[e] == 0 ){
			return false;
		}else{
			s[e]--;
		}
	}
	return true;
}

// v[k](k番目の合計が10になる組合せ)を使う
void used(int k, vector<int> &s){
	for(int i = 0 ; i < vv[k].size() ; i++ ){
		int e = vv[k][i];
		if( s[e] ) s[e]--;
	}
}

int foo;

set<vector<int> > mm;

// DFS
void dfs(int &res, int cnt, int sum, vector<int> &s){
	// 解の更新
	res = max(res, cnt);
	
	if( mm.count(s) ) return;
	
	//if( foo < 100000 ){
		mm.insert(s);
	//}
	
	foo++;
	//if( 7500000 < foo ) return;
	
	if( sum < 10 ) return;
	// もう解が更新できない時点で探索打ち切る
	if( cnt + sum / 10 <= res ) return;
	
	for(int i = 0 ; i < vv.size() ; i++ ){
		if( memo[i] ) continue;
		
		if( check(i, s) ){
			vector<int> s_ = s;
			used(i, s_);
			dfs(res, cnt + 1, sum - v_sum[i], s_);
		}
	}
}

int solve(vector<int> &s){
	foo = 0;
	int sum = 0, res = 0;
	for(int i = 0 ; i < vv.size() ; i++ ){
		if( !check(i, s) ){
			memo[i] = true;
		}
	}
	
	mm.clear();
	for(int i = 1 ; i <= 9 ; i++ ) sum += i * s[i];
	dfs(res, 0, sum, s);
	return res;
}

int main(){
	// 3個以上で10になる饅頭の組合せを事前に列挙しておく
	init();
	
	int n;
	while( cin >> n, n ){
		
		// s[k] := 重さkの饅頭の個数
		vector<int> s(12, 0);
		fill(memo, memo + 40, false);
		
		for(int i=0 ; i < n ; i++ ){
			int e;
			cin >> e;
			s[e]++;
		}
		
		int ans = 0;
		// 2個で10になる組合せは貪欲に使う
		for(int i = 1 ; i <= 4 ; i++ ){
			int j = 10 - i;
			int k = min(s[i], s[j]);
			s[i] -= k;
			s[j] -= k;
			ans += k;
		}
		ans += s[5]/2;
		s[5] %= 2;
		// 3個以上で10になる組合せを探索する
		ans += solve(s);
		// 出力
		cout << ans << endl;
	}	
}