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 JAVA):

Solution:
import static java.util.Arrays.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	void solve() {
	for (;;) {
		int n = sc.nextInt();
		if (n == 0) return;
		int[] a = sc.nextIntArray(n);
		int[] b = new int[10];
		for (int x : a) b[x]++;
		int res = b[5] / 2;
		b[5] %= 2;
		for (int i = 1; i <= 4; i++) {
			int m = Math.min(b[i], b[10 - i]);
			b[i] -= m;
			b[10 - i] -= m;
			res += m;
		}
		patternList = new java.util.ArrayList<int[][]>();
		make(b);
		md = 0;
		int sum = 0;
		for (int i = 0; i < 10; i++) sum += i * b[i];
		search(b, 0, 0, sum);
		System.out.println(res + md);
	}
	}
	int md;
	void search(int[] b, int depth, int ten, int sum) {
		if (depth == patternList.size()) {
			if (md < ten) {
				md = ten;
			}
			return;
		}
		if (ten + sum / 10 <= md) return;
		int[][] p = patternList.get(depth);
		int[] org = b.clone();
		for (int i = 0; ; i++) {
			search(b, depth + 1, ten + i, sum - i * 10);
			boolean ok = true;
			for (int[] k : p) {
				b[k[0]] -= k[1];
				if (b[k[0]] < 0) ok = false;
			}
			if (!ok) break;
		}
		for (int i = 0; i < b.length; i++) b[i] = org[i];
	}

	List<int[][]> patternList;
	void make(int[] b) {
		int[] pattern = new int[10];
		dfs(b, pattern, 0, 0);
	}

	void dfs(int[] b, int[] pattern, int depth, int sum) {
		if (sum == 10) {
			if (depth > 2) {
				int[] hist = new int[10];
				for (int i = 0; i < depth; i++) {
					hist[pattern[i]]++;
				}
				int nz = 0;
				for (int i = 0; i < hist.length; i++) if (hist[i] > 0) nz++;
				int[][] k = new int[nz][2];
				int sz = 0;
				for (int i = 0; i < hist.length; i++) if (hist[i] > 0) {
					k[sz][0] = i;
					k[sz][1] = hist[i];
					sz++;
				}
				patternList.add(k);
			}
			return;
		}
		int s = (depth == 0) ? 1 : pattern[depth-1];

		for (int i = s; i <= 9; i++) if (b[i] > 0 && sum + i <= 10) {
			pattern[depth] = i;
			dfs(b, pattern, depth + 1, sum + i);
			pattern[depth] = 0;
		}
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}