You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在中国 8 是一个吉利数字，新年将至鼠鼠想要获得尽可能多的吉利数字，鼠鼠能力有限，所以 8 的倍数也被认为是吉利数字。

现在鼠鼠有$n$个数字 $a_i$，鼠鼠可以选择两个不同的数$x,y$，并把$a_x,a_y$组合成$a_x+a_y$。

请问鼠鼠有多少种方法可以组合出吉利数字?

注意$x=1,y=2$和$x=2,y=1$被认为是一种方案

Format

Input

第一行一个n

然后 n 行每行一个数字 $a_i$ 对于25%的数据保证 $1 \leq n \leq 1000,1 \leq a_i \leq 10^6$ 对于100%的数据保证 $1\leq n \leq 10^5,1\leq a_i \leq 10^{9}$

Output

输出一个数，表示方案数

Samples

5
2
4
2
4
6

3

Limitation

1s, 1024KiB for each test case.