#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;
}    

Measured memory_bytes: 32904