背景

GESP三级真题(202403)

描述

小杨同学有一个包含 $n$ 个非负整数的序列 $A$ ，他想要知道其中有多少对下标组合 $<i, j>(1 \le i, j \le n, i < j)$ ，使得$A_i + A_j$ 是完全平方数。

如果 $x$ 是完全平方数，则存在非负整数 $y$ 使得 $y \times y = x$ 。

格式

输入

第一行一个非负整数 ，表示非负整数个数。

第二行包含 个非负整数$A_1,A_2, ...., A_n$，表示序列 $A$ 包含的非负整数。

输出

输出一个非负整数，表示和是完全平方数的非负整数对数。

样例

5 
1 4 3 3 5

3

数据规模

对于全部数据，保证 $1 \le n \le 1000, 0 \le A_i \le 10^5$。

限制

时间限制：1.0 s

空间限制：128.0 MB