Type: Default 1000ms 256MiB

L1-3 吉利的8

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 的倍数也被认为是吉利数字。

现在鼠鼠有nn个数字 aia_i,鼠鼠可以选择两个不同的数x,yx,y,并把ax,aya_x,a_y组合成ax+aya_x+a_y

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

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

Format

Input

第一行一个n

然后 n 行每行一个数字 aia_i 对于25%的数据保证 1n1000,1ai1061 \leq n \leq 1000,1 \leq a_i \leq 10^6 对于100%的数据保证 1n105,1ai1091\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.