苹果种植户 Ingrid 刚刚收获了大量的苹果，她打算把这些苹果分给自己和邻居们。她的街区可以用一个无限平面表示，其中每个整数坐标点都恰好有一栋房子。Ingrid 的房子位于原点 $(0, 0)$。Ingrid 在分发苹果时有一种特殊的策略。首先，她选择一个由 $n$ 个非负整数组成的列表 $r_1, r_2, \dots, r_n$。对于列表中的每个数字 $r_i$，她会向半径 $r_i$ 范围内的每栋房子分发一个苹果，即坐标满足 $x^2 + y^2 \le r_i^2$ 的每栋房子（包括她自己的房子）。这样，Ingrid 较近的邻居会比远处的邻居得到更多的苹果。

Ingrid 刚刚选好了半径列表，但随后出现了一个问题。在分发苹果时，她总是将它们装在立方体盒子中，每个盒子装八个苹果。因此，分发的苹果总数是 8 的倍数这一点非常重要。Ingrid 需要从列表中移除一些半径，使得分发的苹果总数成为 8 的倍数。这总是可行的，例如通过移除所有半径，但 Ingrid 不想显得太贪心，因此她希望以一种能够最小化“原本计划分发但最终未分发的苹果数量”的方式来移除半径。你的任务是找到这个最小值。

输入格式

• 第 1 行：整数 $N$，即半径的数量（$1 \le N \le 3 \cdot 10^5$）。
• 第 2 行：空格分隔的整数 $r_1, r_2, \dots, r_N$（$0 \le r_i \le 3 \cdot 10^5$）。

输出格式

• 输出一个整数，表示 Ingrid 通过从列表中移除半径，在使分发的苹果总数成为 8 的倍数的前提下，能够不分发的苹果的最小数量。

样例

输入样例 1

6
1 0 2 1 0 0

输出样例 1

2

说明

在半径为 0 的范围内有 1 栋房子，半径为 1 的范围内有 5 栋房子，半径为 2 的范围内有 13 栋房子。因此，在这些半径范围内总共有 26 栋房子。通过移除两个半径 0，还剩下 24 栋房子。

子任务

你的解法将在一组测试点（子任务）上进行测试。要获得某个子任务的分数，你需要通过该子任务中的所有测试点。