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 <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#include <cstring>
#include <cassert>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

const int CANDICATE_N = 36;
// 最初の6個は5を含む
int a[CANDICATE_N] = {65808, 69633, 65569, 65794, 65555, 65541, 277, 52, 4116, 516, 1048580, 291, 4102, 4355, 16777219, 66, 4130, 530, 1048594, 38, 8194, 268435458, 305, 263, 4369, 16777233, 769, 1048833, 24, 80, 4144, 544, 1048608, 10, 8208, 4608};

int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
int N, manju[10];
int rest[4], rest_b, base[4];
char dp[902394][CANDICATE_N];

// i: a_index, j: rest_index
inline int at(int i, int j){
    if(rest[j] == 0){return 0;}
    // if(CANDICATE_N <= i || i < 0 || 4 <= j && j < 0){puts("-1"); exit(0);}
    return a[i] >> (4*(rest[j]-1)) & 0xf;
}

// i: rest_index
inline int at2(int i){
    if(rest[i] == 0){return 0;}
    // if(4 <= i || i < 0){puts("-1"); exit(0);}
    return manju[rest[i]];
}

// i: a_index, j: rest_index
inline int at3(int i, int j){
    if(rest[j] == 0){return 0;}
    // if(CANDICATE_N <= i || i < 0 || 4 <= j && j < 0){puts("-1"); exit(0);}
    return at2(j) - at(i, j);
}

inline char& at4(int i, int j, int k, int l, int index){
    // if(i+base[0]*(j+base[1]*(k+base[2]*l)) >= 902394){puts("-1"); exit(0);}
    // return dp[i+26*(j+26*(k+26*l))][index];
    return dp[i+base[0]*(j+base[1]*(k+base[2]*l))][index];
}

inline int at5(int i, int j){
    if(j == 0){return 0;}
    // if(CANDICATE_N <= i || i < 0 || 4 <= j && j < 0){puts("-1"); exit(0);}
    return a[i] >> (4*(j-1)) & 0xf;
}

inline bool can(int a, int b, int c, int d, int index){
    FOR(i, 1, 9){
        //printf("index=%d, i=%d (in can)\n", index, i);
        if(i == 5){continue;}
        if(!(rest_b >> i & 1) && at5(index, i) > 0){return false;}
    }

    if(at(index, 0) == 0 && at(index, 1) == 0 &&
       at(index, 2) == 0 && at(index, 3) == 0){;return false;}

    return a >= at(index, 0) &&
        b >= at(index, 1) &&
        c >= at(index, 2) &&
        d >= at(index, 3);
}

char rec(int a, int b, int c, int d, int index){
    if(index == CANDICATE_N){return 0;}
    if(a == 0 && b == 0 && c == 0 && d == 0){return 0;}
    if(at4(a, b, c, d, index) != -1){return at4(a, b, c, d, index);}
    
    char res = rec(a, b, c, d, index+1);
    if(can(a, b, c, d, index)){
        res = std::max(res, static_cast<char>(rec(a-at(index, 0), b-at(index, 1), c-at(index, 2), d-at(index, 3), index)+1));
    }

    return at4(a, b, c, d, index) = res;
}

int main(){
    while(std::cin >> N, N){
        memset(manju, 0, sizeof(manju));

        REP(i, N){
            int w;
            std::cin >> w;

            manju[w] += 1;
        }

        // FOR(i, 1, 10){printf("%d: %d\n", i, manju[i]);}

        char r1 = 0;
        FOR(i, 1, 5){
            int mn = std::min(manju[i], manju[10-i]);
            r1 += mn;
            manju[i] -= mn; manju[10-i] -= mn;
        }

        r1 += manju[5] >> 1;
        manju[5] &= 1;

        {
            int n = 0;
            std::fill(rest, rest+4, 0);
            rest_b = 0;
            FOR(i, 1, 10){
                if(i == 5 || i == 9){continue;}
                if(manju[i] > 0){
                    rest[n] = i;
                    rest_b |= 1 << i;
                    n += 1;
                }
            }

            std::sort(rest, rest+4);

            REP(i, 4){
                for(int p : prime){if(manju[rest[i]] < p){base[i] = p; break;}}
            }
        }

        memset(dp, -1, sizeof(dp));

        char r2 = rec(at2(0), at2(1), at2(2), at2(3), 6);
        if(manju[5] == 1){
            REP(i, 6){
                if(can(at2(0), at2(1), at2(2), at2(3), i)){
                    r2 = std::max(r2, static_cast<char>(rec(at3(i, 0), at3(i, 1), at3(i, 2), at3(i, 3), 6) + 1));
                }
            }
        }

        std::cout << (r1+r2) << std::endl;
    }

    return 0;
}