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 <cstdio>
#include <map>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

typedef unsigned long long ull;

map<ull,int> memo;

int dfs2(ull, int, int);

int dfs1(ull s){
	if(s <= 0xff){
		return s / 10;
	}
	if(memo.count(s)){
		return memo[s];
	}
	int k;
	for(k = 8; !(s >> ((k - 1) * 8)); --k);

	int a = dfs2(s - (1ull << ((k - 1) * 8)), 10 - k, k);
	int b = dfs1(s & ((1ull << ((k - 1) * 8)) - 1));
	int res = max(a, b);

	memo[s] = res;
	return res;
}

int dfs2(ull s, int t, int u){
	if(t != 9 && s >> ((t - 1) * 8) & 0xff){
		return dfs1(s - (1ull << ((t - 1) * 8))) + 1;
	}
	if(t == 1){
		return 0;
	}
	if(t == 2){
		if((s & 0xff) >= 2){
			return dfs1(s - 2) + 1;
		}
		return 0;
	}
	if(t == 3){
		if(s & 0xff && s & 0xff00){
			return dfs1(s - 0x101) + 1;
		}
		if((s & 0xff) >= 3){
			return dfs1(s - 3) + 1;
		}
		return 0;
	}
	
	int res = 0;
	for(u = min(t, u); u >= 1; --u){
		if(s >> ((u - 1) * 8) & 0xff){
			int a = dfs2(s - (1ull << ((u - 1) * 8)), t - u, u);
			res = max(res, a);
		}
	}
	return res;
}

int main(){
	int n, x;
	while(scanf("%d", &n), n){
		int cnt[10] = {};
		for(int i = 0; i < n; ++i){
			scanf("%d", &x);
			++cnt[x];
		}
		
		int ans = 0;
		x = min(cnt[1], cnt[9]);
		cnt[1] -= x;
		cnt[9] -= x;
		ans = x;
		
		ull s = 0;
		for(int i = 1; i <= 8; ++i){
			s |= (ull)cnt[i] << ((i - 1) * 8);
		}
		
		memo.clear();
		ans += dfs1(s);
		printf("%d\n", ans);
	}
}