Problem J
Game of Nines

You are playing a simple game of adding digits. You are given a list of single digits between $0$ and $8$ (inclusive). In each move, you may choose any two digits $a$ and $b$, add $a$ to $b$, and replace $b$ with the sum $a + b$. If $a + b \geq 10$, keep only the units digit (e.g. $5 + 8$ becomes $3$; $4 + 6$ becomes $0$). Whenever the sum is $9$, the result is eliminated immediately and cannot participate in further additions. Note that you cannot add a digit to itself. However, you may choose two digits $a$ and $b$ that have the same value.

Your goal is to eliminate as many digits as possible, using any number of moves.

Input

The first line of input contains a single integer $n$ ($2 \leq n \leq 1\, 000$), the number of digits. Each of the next $n$ lines contains a single digit between $0$ and $8$, forming the initial list of digits.

Output

Output a single integer, the minimum number of digits that will remain if you play optimally to eliminate as many digits as possible.

Explanation of Sample Case 1

Add $3$ to $6$ and eliminate one digit ($3 + 6$ becomes $9$). The remaining digits are $2$ and $3$. Then add $2$ to $3$ three times ($3 + 2$ becomes $5$, $5 + 2$ becomes $7$, $7 + 2$ becomes $9$). The single digit remaining is $2$. It is also possible to eliminate two digits with a different sequence of moves.

3
2
3
6

1

2
4
4

2