题目描述

wtr1 和 wqh 是一对好朋友。

wqh 给了 wtr1 一个长度为 $n$ 的数组 $A$。对于 $i=1,2,\dots,n$，需要 wtr1 给出包含了位置 $i$ 且区间和为完全平方数的子数组个数。由于最近 wtr1 很忙，请聪明的你帮帮他吧！

若一个数是一个整数的平方，则称这个数是完全平方数。

原数组中某段下标连续的元素按原顺序构成的数组称为子数组。

输入格式

第一行输入一个正整数 $n$，表示数组 $A$ 的长度。

第二行输入 $n$ 个整数 $A_1,\dots,A_n$，表示 $A$ 中的元素。

输出格式

输出 $n$ 行，每行包含一个非负整数，表示符合条件的区间数。

5
1 2 3 4 5

1
1
1
3
1

说明/提示

【样例解释 #1】

包含位置 $2$ 的区间和为完全平方数是 $2+3+4=9$，只有 $1$ 个。

包含位置 $4$ 的区间和为完全平方数是 $2+3+4=9$，$4+5=9$ 以及 $4$ 本身，共 $3$ 个。

【数据范围】

• $1 \le n \le 5 \times 10^3$。
• $0 \le a_i \le 10^9$。