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 ≥ 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, but 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 ≤ n ≤ 1000), 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 → 5

• 5 + 2 → 7

• 7 + 2 → 9 (eliminated)

The single digit remaining is 2. It is also possible to eliminate two digits with a different sequence of moves.

Sample Input 1

3
2
3
6

Sample Output 1

1

Sample Input 2

2
4
4

Sample Output 2

2