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 <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
vint a;
vector<vvint> vv;
vint tmp;
typedef unsigned long long ull;
map<ull,int> ma;
VV(pii) vp;
int cnt=0;
void foo(int a,int b){
	// if(a>9) return;
	if(b==10){
		vv[a].PB(tmp);
		// cout<<cnt++<<endl;;
		return;
	}
	if(b>10){
		return;
	}
	reep(i,1,10){
		if(b+i>10) break;
		tmp.PB(i);
		foo(a+1,b+i);
		tmp.pop_back();
	}
}
ull bb=1145148931919;
ull hash(){
	ull ret=0;
	rep(i,10){
		ret*=bb;
		ret+=a[i];
	}
	return ret;
}
int dfs(int t1){
	ull aa=hash();
	if(ma.count(aa)) return ma[aa];
	// if(y<2) return ma[aa]=0;
	// if(y<2) return 0;
	int ret=0;
	reep(i,t1,vp.size()){
		bool f=true;
		rep(j,vp[i].size()){
			f&=(0<=(a[vp[i][j].F]-=vp[i][j].S));	
		}
		if(f){
			ret=max(ret,dfs(i)+1);
		}
		rep(j,vp[i].size()){
			a[vp[i][j].F]+=vp[i][j].S;
		}
	}
	// reep(j,t2,vp[t1].size()){
		// rep(k,vp[t1][j].size()){
			// a[vp[t1][j][k].F]-=vp[t1][j][k].S;
		// }
		// bool f=true;
		// reep(k,1,10){
			// if(a[k]<0) f=false;
		// }
		// if(f){
			// ret=max(ret,dfs(y-t1,t1,j)+1);
		// }
		// rep(k,vp[t1][j].size()){
			// a[vp[t1][j][k].F]+=vp[t1][j][k].S;
		// }
	// }
	// reep(i,t1+1,11){
		// rep(j,vp[i].size()){
			// rep(k,vp[i][j].size()){
				// a[vp[i][j][k].F]-=vp[i][j][k].S;
			// }
			// bool f=true;
			// reep(k,1,10){
				// if(a[k]<0) f=false;
			// }
			// if(f){
				// ret=max(ret,dfs(y-i,i,j)+1);
			// }
			// rep(k,vp[i][j].size()){
				// a[vp[i][j][k].F]+=vp[i][j][k].S;
			// }
		// }
	// }
	return ma[aa]=ret;
	// return ret;
}
void mainmain(){
	int n;
	vv=vector<vvint>(11);
	foo(0,0);
	rep(i,vv.size()){
		rep(j,vv[i].size()){
			sort(ALL(vv[i][j]));
		}
		sort(ALL(vv[i]));
		vv[i].erase(unique(ALL(vv[i])),vv[i].end());
	}
	rep(i,vv.size()){
		VV(pii) tmp;
		rep(j,vv[i].size()){
			int t1=vv[i][j][0];
			int t2=0;
			vector<pii> vpii;
			rep(k,vv[i][j].size()){
				if(t1==vv[i][j][k]){
					t2++;
				}
				else{
					vpii.PB(pii(t1,t2));
					t1=vv[i][j][k];
					t2=1;
				}
			}
			vpii.PB(pii(t1,t2));
			tmp.PB(vpii);
		}
		rep(i,tmp.size()){
			vp.PB(tmp[i]);
		}
	}
	// rep(i,vp.size()){
		// cout<<endl;
		// cout<<"i "<<i<<endl;
		// rep(j,vp[i].size()){
			// cout<<" j "<<j<<endl;
			// rep(k,vp[i][j].size()){
				// cout<<"  "<<vp[i][j][k].F<<" "<<vp[i][j][k].S<<endl;
			// }
		// }
	// }
	// return;
	while(cin>>n,n){
		ma.clear();
		// cout<<n<<endl;
		vint v(n);
		rep(i,n) cin>>v[i];
		a=vint(10,0);
		rep(i,n){
			a[v[i]]++;
		}
		int ans1=0;
		reep(i,1,5){
			while(a[i]&&a[10-i]) ans1++,a[i]--,a[10-i]--;
		}
		while(a[5]>=2) ans1++,a[5]-=2;
		// rep(i,vv[3].size()){
			// bool f=true;
			// while(f){
				// rep(j,vv[3][i].size()){
					// f&=0<=(--a[vv[3][i][j]]);
				// }
				// if(!f){
					// rep(j,vv[3][i].size()){
						// ++a[vv[3][i][j]];
					// }
					// break;
				// }
				// ans1++;
			// }
		// }
		int ans2=dfs(0);
		// reep(i,2,11){
			// for(int j=vv[i].size()-1;j>=0;j--){
				// bool f=true;
				// rep(k,vv[i][j].size()){
					// a[vv[i][j][k]]--;
				// }
				// rep(k,10){
					// if(a[k]<0) f=false;
				// }
				// if(f){
					// ans++;
				// }
				// else{
					// rep(k,vv[i][j].size()){
						// a[vv[i][j][k]]++;
					// }
				// }
			// }
		// }
		cout<<ans1+ans2<<endl;
	}
}



}
int main() try{
    mainmain();
}
catch(...){
}