#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;

#define REP(i,s,t) for(int i=(s);i<(t);i++)
#define FILL(x,v) memset(x,v,sizeof(x))

bool v[9][9][9], v2[9][9];
void solve2(VI ds) {
  sort(ds.begin(), ds.end());
  if (ds[0] == 1 || ds.back() == 9) {
    v2[1][1] = true;
    return;
  }
  assert(ds[1] < 9);
  if (v2[ds[0]][ds[1]]) return;
  v2[ds[0]][ds[1]] = true;
  solve2(VI({(ds[0] + ds[1])%10, ds[1]}));
  solve2(VI({ds[0], (ds[0] + ds[1])%10}));
}
void solve(VI ds){
  sort(ds.begin(), ds.end());
  if (ds.back() == 9) {
    FILL(v2, false);
    solve2(VI({ds[0], ds[1]}));
    if (v2[1][1]) v[1][1][1] = true;
    return;
  }
  if (ds[0] == 1) {
    v[1][1][1] = true;
    return;
  }
  assert(ds[2] < 9);
  if (v[ds[0]][ds[1]][ds[2]]) return;
  v[ds[0]][ds[1]][ds[2]] = true;
  REP(i,0,3) REP(j,i+1,3) {
    int k = 3 ^ i ^ j;
    VI nds = ds;
    nds[k] = (nds[i] + nds[j]) % 10;
    solve(nds);
  }
}

int main() {
  int n, a;
  cin >> n;

  VI cnt(9, 0), as;
  REP(i,0,n) {
    cin >> a;
    cnt[a]++;
    as.push_back(a);
  }

  for (auto a: as) for (auto b: as) {
    FILL(v2, false);
    solve2(VI({a,b}));
    if (v2[1][1]) {
      cout << 1 << endl;
      return 0;
    }
  }
  REP(a,0,9) REP(b,a,9) REP(c,b,9) {
    VI need(9, 0);
    need[a]++; need[b]++; need[c]++;
    bool ok = true;
    REP(d,0,9) if(need[d] > cnt[d]) ok = false;
    if (!ok) continue;

    FILL(v, false);
    solve(VI({a,b,c}));
    if (v[1][1][1]) {
      cout << 1 << endl;
      return 0;
    }
  }
  cout << n << endl;
  return 0;
}