你正在玩一个简单的数字相加游戏。给你一个由介于 $0$ 到 $8$（含）之间的个位数组成的列表。在每一步操作中，你可以选择任意两个数字 $a$ 和 $b$，将 $a$ 加到 $b$ 上，并将 $b$ 替换为和 $a + b$。如果 $a + b \ge 10$，则只保留个位数（例如，$5 + 8$ 变为 $3$；$4 + 6$ 变为 $0$）。每当和为 $9$ 时，该结果会立即被消除，且不能再参与后续的相加。

你的目标是通过任意次数的操作，消除尽可能多的数字。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 1\,000$），表示数字的个数。

接下来的 $n$ 行，每行包含一个介于 $0$ 到 $8$ 之间的个位数，构成初始的数字列表。

输出格式

输出一个整数，表示如果你以最优策略操作以消除尽可能多的数字，最后剩下的最少数字个数。

样例

输入格式 1

3
2
3
6

输出格式 1

1

说明

将 $3$ 加到 $6$ 上并消除一个数字（$3+6$ 变为 $9$）。剩下的数字是 $2$ 和 $3$。然后将 $2$ 加到 $3$ 上三次（$3+2$ 变为 $5$，$5+2$ 变为 $7$，$7+2$ 变为 $9$）。最后剩下的单个数字是 $2$。通过不同的操作顺序，也可以消除两个数字。

输入格式 2

2
4
4

输出格式 2

2