Background

Special for beginners, ^_^

Description

给出 $N（\le2\times10^5）$ 个非负整数 $a_i（\le2\times10^5）$ ，问能找到多少对 $(i, j)$ 满足 $i < j$ 且 $a_i\times a_j$ 是一个完全平方数。

Format

Input

第一行给出一个整数 $N$ 表示数组大小。

第二行 $N$ 个非负整数 $a_i$ 。

Output

一行一个答案。

Samples

4
1 2 3 4

1

Limitation

1s, 1024KiB for each test case.